#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
template <class T>
inline T lowbit(T x) {
  return x & (-x);
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline bool scan(T &ret) {
  char c;
  int sgn;
  if (c = getchar(), c == EOF) return 0;
  while (c != '-' && (c < '0' || c > '9')) c = getchar();
  sgn = (c == '-') ? -1 : 1;
  ret = (c == '-') ? 0 : (c - '0');
  while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
  ret *= sgn;
  return 1;
}
const double pi = 3.14159265358979323846264338327950288L;
using namespace std;
long long f[233];
bool is_prime(long long n) {
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}
int ans;
int dfs(long long n) {
  if (n == 2 || n == 3 || n == 5 || n == 7) {
    return 1;
  }
  if (n <= 10) {
    return 2;
  }
  if (is_prime(n)) return 1;
  if (n % 2 == 0) return 2;
  if (is_prime(n - 2)) return 2;
  return 3;
}
int main() {
  long long n;
  cin >> n;
  ans = dfs(n);
  cout << ans << endl;
  return 0;
}
