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