#include <bits/stdc++.h>
int n;
bool isPrime(int val) {
  int lim = sqrt(val), cnt = 0;
  for (int i = 1; i <= lim; i++)
    if (val % i == 0) cnt++;
  return cnt == 1;
}
int main() {
  scanf("%d", &n);
  if (isPrime(n))
    printf("1");
  else if (n % 2 == 0 || isPrime(n - 2))
    printf("2");
  else
    printf("3");
}
