#include <bits/stdc++.h>
using namespace std;
bool prime(long long int n) {
  int flag = 1;
  for (int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) {
      flag = 0;
      break;
    }
  }
  if (flag == 1)
    return true;
  else
    return false;
}
int main() {
  long long int n, k, m, flag = 1;
  cin >> n;
  if (n % 2 == 0) {
    if (prime(n))
      cout << 1;
    else
      cout << 2;
  } else {
    if (prime(n))
      cout << 1;
    else {
      if (prime(n - 2))
        cout << 2;
      else
        cout << 3;
    }
  }
}
