#include <bits/stdc++.h>
int prime(int n) {
  for (int s = 2; s * s <= n; s++) {
    if (n % s == 0) {
      return 0;
    }
  }
  return 1;
}
int solve(int n) {
  if (prime(n)) {
    return 1;
  }
  if (~n & 1) {
    return 2;
  }
  return prime(n - 2) ? 2 : 3;
}
int main() {
  int n = 0;
  scanf("%d", &n);
  printf("%d\n", solve(n));
  return 0;
}
