#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
bool pr(int k) {
  for (int l = 2; l * l <= k; l++) {
    if (k % l == 0) return false;
  }
  return true;
}
int main() {
  int n;
  cin >> n;
  if (pr(n)) {
    cout << 1;
    return 0;
  } else if (n % 2 == 0) {
    cout << 2;
    return 0;
  } else {
    if (pr(n - 2)) {
      cout << 2;
    } else
      cout << 3;
  }
}
