#include <bits/stdc++.h>
using namespace std;
template <typename G1, typename G2 = G1, typename G3 = G1>
struct triple {
  G1 first;
  G2 second;
  G3 T;
};
int main() {
  int N = 1e5;
  vector<bool> sieve(N);
  vector<int> p;
  for (int i = 2; i < N; i++)
    if (!sieve[i]) {
      p.push_back(i);
      for (long long j = (long long)i * i; j < N; j += i) sieve[j] = true;
    }
  auto is_prime = [&](int x) {
    bool prime = true;
    for (int i = 0; i < p.size() && p[i] < x && (long long)p[i] * p[i] <= x;
         i++)
      if (x % p[i] == 0) {
        prime = false;
        break;
      }
    return prime;
  };
  const int M = 1e4;
  vector<int> dp(M, 1e9);
  dp[1] = dp[2] = dp[3] = 1;
  for (int i = 4; i < M; i++) {
    if (!sieve[i])
      dp[i] = 1;
    else {
      for (auto j : p)
        if (i - j >= 2)
          dp[i] = min(dp[i], 1 + dp[i - j]);
        else
          break;
    }
  }
  int n;
  cin >> n;
  if (n < M)
    cout << dp[n] << '\n';
  else if (is_prime(n))
    cout << "1\n";
  else {
    int ans = 1e9;
    for (int i = n - 2; i >= 2 && i > n - M; --i)
      if (is_prime(i)) ans = min(ans, 1 + dp[n - i]);
    cout << ans << '\n';
  }
  return 0;
}
