#include <bits/stdc++.h>
using namespace std;
int isprime(int n) {
  if (n == 2) return 1;
  if (n % 2 == 0) return 0;
  for (int d = 3; d * d <= n; d += 2)
    if (n % d == 0) return 0;
  return 1;
}
int go(int n) {
  if (isprime(n)) return 1;
  if (n % 2 == 0) return 2;
  if (isprime(n - 2)) return 2;
  return 3;
}
int main() {
  int n;
  scanf("%d", &n);
  printf("%d\n", go(n));
}
