#include <bits/stdc++.h>
using namespace std;
bool prime(int n) {
  if (n == 2) return 1;
  if (n == 1 || n % 2 == 0) return 0;
  for (int i = 3; i * i <= n; i += 2) {
    if (n % i == 0) return 0;
  }
  return 1;
}
int n;
int main() {
  cin >> n;
  if (prime(n)) {
    cout << 1;
    return 0;
  }
  if (n % 2 == 0)
    cout << 2;
  else {
    if (n - 2 > 1 && prime(n - 2)) {
      cout << 2;
    } else
      cout << 3;
  }
  return 0;
}
