#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50 * 1001, MOD = 30011;
int dp[MAXN], mark[MAXN];
vector<int> p;
inline bool isp(int x) {
  for (auto u : p) {
    if (u == x) break;
    if (x % u == 0) return 0;
  }
  return 1;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 2; i < MAXN; i++) {
    if (!mark[i]) {
      p.push_back(i);
      for (int j = i; j < MAXN; j += i) mark[j] = 1;
    }
  }
  if (isp(n)) return cout << 1, 0;
  if (n % 2 == 0) return cout << 2, 0;
  if (isp(n - 2)) return cout << 2, 0;
  cout << 3;
}
