#include <bits/stdc++.h>
using namespace std;
const int MN = 200000 + 10;
const int MOD = 1000000007;
long long n;
long long mul_mod(long long x, long long y, long long n) {
  long long ret = 0, tmp = x % n;
  while (y) {
    if (y & 1)
      if ((ret += tmp) > n) ret -= n;
    if ((tmp <<= 1) > n) tmp -= n;
    y >>= 1;
  }
  return ret;
}
long long pow_mod(long long a, long long b, long long c) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = mul_mod(ret, a, c);
    a = mul_mod(a, a, c);
    b >>= 1;
  }
  return ret;
}
bool is_prime(long long n, int t = 10) {
  if (n == 2) return true;
  if (n < 2 || !(n & 1)) return false;
  long long k = 0, m, a, i;
  for (m = n - 1; !(m & 1); m >>= 1, k++)
    ;
  while (t--) {
    a = pow_mod(rand() % (n - 2) + 2, m, n);
    if (a != 1) {
      for (i = 0; i < k && a != n - 1; i++) a = mul_mod(a, a, n);
      if (i >= k) return false;
    }
  }
  return true;
}
int main() {
  scanf("%lld", &n);
  if (is_prime(n)) {
    printf("1\n");
    return 0;
  }
  if (is_prime(n - 2)) {
    printf("2\n");
    return 0;
  }
  if (n % 2)
    printf("3\n");
  else
    printf("2\n");
  return 0;
}
