#include <bits/stdc++.h>
using namespace std;
int x, ans;
bool judge(const int& x) {
  if (x < 2) return false;
  if (x == 2) return true;
  for (int i = 2; i * i <= x; ++i)
    if (x % i == 0) return false;
  return true;
}
signed main() {
  scanf("%d", &x);
  printf("%d", judge(x) ? 1 : x & 1 ? judge(x - 2) ? 2 : 3 : 2);
  return 0;
}
