#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
  int m = n;
  int sq = sqrt(m);
  int i;
  for (i = 2; i <= sq; ++i) {
    if (n % i == 0) return 0;
  }
  return 1;
}
int main() {
  int n;
  scanf("%d", &n);
  if (n % 2 == 0 && n != 2)
    puts("2");
  else if (isPrime(n)) {
    puts("1");
  } else if (isPrime(n - 2))
    puts("2");
  else
    puts("3");
  return 0;
}
