#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T lowbit(T x) {
  return x & (-x);
}
int main(void) {
  int n;
  scanf("%d", &n);
  bool is_prime = true;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      is_prime = false;
      break;
    }
  }
  if (is_prime) {
    puts("1");
    return 0;
  } else {
    if (n % 2 == 0) {
      puts("2");
      return 0;
    } else {
      is_prime = true;
      for (int i = 2; i * i <= n - 2; i++) {
        if ((n - 2) % i == 0) {
          is_prime = false;
          break;
        }
      }
      if (is_prime) {
        puts("2");
      } else {
        puts("3");
      }
    }
  }
  return 0;
}
