#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int grand(int x) { return uniform_int_distribution<int>(0, x - 1)(rng); }
long long gcd(long long x, long long y) {
  if (x < y) return gcd(y, x);
  if (y == 0) return x;
  return gcd(y, x % y);
}
const long long mod = 1e9 + 7;
long long modexp(long long x, long long ex) {
  long long ans = 1ll;
  while (ex > 0) {
    if (ex & 1ll) ans = (ans * x) % mod;
    ex >>= 1ll;
    x = (x * x) % mod;
  }
  return ans;
}
const int maxn = 1e6 + 7;
const long long inf = 1e9 + 7;
int main() {
  {
    ios ::sync_with_stdio(false);
    cin.tie(0);
  };
  long long n;
  cin >> n;
  bool isp = true;
  for (long long x = 2; x * x <= n; x++) {
    if (n % x) continue;
    isp = false;
  }
  if (isp) {
    cout << 1 << "\n";
    return 0;
  }
  if (n % 2) {
    bool isp = true;
    long long m = n - 2;
    for (long long x = 2; x * x <= m; x++) {
      if (m % x) continue;
      isp = false;
    }
    if (isp) {
      cout << 2 << "\n";
      return 0;
    }
  }
  if (n % 2) {
    cout << 3 << "\n";
  } else {
    cout << 2 << "\n";
  }
}
