#include <bits/stdc++.h>
using namespace std;
const int inf = int(1e9);
const double eps = 0.0000000001, pi = 3.14159265358979323;
inline bool check(int v) {
  for (long long i = 2; i * i <= v; ++i) {
    if (v % i == 0) return false;
  }
  return true;
}
inline int Find(int v) {
  int mx = 0;
  for (int i = 2; i * i <= v; ++i) {
    if (v % i == 0) {
      mx = max(mx, i);
      mx = max(mx, v / i);
    }
  }
  return mx;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, f, s, res = inf;
  cin >> n;
  if (check(n)) {
    res = 1;
  }
  if (check(n - 2)) {
    res = min(res, 2);
  }
  if (n % 2 == 0) {
    res = min(res, 2);
  } else {
    res = min(res, 3);
  }
  cout << res;
  return 0;
}
