#include <bits/stdc++.h>
using namespace std;
bool prime(long long int n) {
  if (n <= 1LL) return false;
  if (n <= 3LL) return true;
  if (n % 2 == 0LL || n % 3 == 0LL) return false;
  for (long long int i = 5LL; (i * i) <= n; i += 6LL) {
    if (n % i == 0LL || n % (i + 2LL) == 0LL) {
      return false;
    }
  }
  return true;
}
int main() {
  ios_base ::sync_with_stdio(false), cin.tie(NULL);
  long long int a;
  cin >> a;
  if (prime(a))
    cout << 1;
  else if (a & 1 and !prime(a - 2))
    cout << 3;
  else
    cout << 2;
  return 0;
}
