#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 9;
const int mod = 1e9 + 7;
const long long MOD = 1e9 + 696969;
const long long INF = 1e18;
const int MAX = 1e6;
int primes[1000100], dp[1000100], fp[1000100];
vector<int> pp;
inline bool isprime(int x) {
  if (x <= 3) return 1;
  int s = sqrt(x) + 1;
  for (auto u : pp) {
    if (x % u == 0) return 0;
    if (u >= s) return 1;
  }
  return 1;
}
int main() {
  primes[0] = primes[1] = 1;
  for (int i = 2; i <= MAX; ++i)
    if (primes[i] == 0) {
      pp.push_back(i);
      for (int j = i + i; j <= MAX; j += i) primes[j] = 1;
    }
  int n;
  cin >> n;
  if (isprime(n)) {
    cout << 1;
    exit(0);
  };
  if (n % 2 == 0) {
    {
      cout << 2;
      exit(0);
    };
  } else {
    if (isprime(n - 2)) {
      cout << 2;
      exit(0);
    };
    {
      cout << 3;
      exit(0);
    };
  }
}
