#include <bits/stdc++.h>
using namespace std;
const int N = 2000500;
bool was[N];
long long binpow(long long x, long long p, long long mod) {
  long long res = 1;
  while (p) {
    if (p & 1) {
      res *= x;
      res %= mod;
    }
    x *= x;
    x %= mod;
    p /= 2;
  }
  return res;
}
bool ferma(long long x) {
  if (x == 1) return false;
  for (int i = 1; i <= 100; i++) {
    int a = rand();
    while (a % x == 0) {
      a = rand();
    }
    if (binpow(a, x - 1, x) != 1) {
      return false;
    }
  }
  return true;
}
int main() {
  srand(time(NULL));
  int n;
  cin >> n;
  vector<int> pi;
  for (int i = 2; i <= 1000000; i++) {
    if (!was[i]) {
      pi.push_back(i);
      int j = i;
      while (j + i <= 1000000) {
        j += i;
        was[j] = 1;
      }
    }
  }
  bool w = 1;
  for (int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) {
      w = false;
    }
  }
  if (w) cout << 1, exit(0);
  for (auto i : pi) {
    if (n - i > 0 && ferma(n - i)) {
      cout << 2, exit(0);
    }
  }
  cout << 3;
  return 0;
}
