#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 105;
bool is_prime(long long num) {
  for (long long i = 2; i * i <= num; i++)
    if (num % i == 0) return false;
  return true;
}
int main() {
  long long n;
  while (cin >> n) {
    if (is_prime(n))
      cout << "1\n";
    else if (n & 1 && (!is_prime(n - 2)))
      cout << "3\n";
    else
      cout << "2\n";
  }
  return 0;
}
