#include <bits/stdc++.h>
int sushu(int x);
int main() {
  int n, m;
  scanf("%d", &n);
  m = sushu(n);
  if (n == 2)
    printf("1\n");
  else if (n % 2 == 0)
    printf("2\n");
  else if (m == n)
    printf("1\n");
  else if ((n - m) == 2)
    printf("2\n");
  else
    printf("3\n");
  return 0;
}
int sushu(int x) {
  int z;
  for (int y = x; y >= 1; y--) {
    for (z = 2; z * z <= y; z++) {
      if (y % z == 0) break;
    }
    if (z * z > y) return y;
  }
}
