#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 1e7 + 1;
;
const long long INF = 2e9 + 10;
const long long MOD = 1000 * 1000 * 1000 + 7;
const long double EPS = 1e-9;
int a[N];
bool prime(int x) {
  for (int i = 2; i < (int)sqrt(x) + 1; ++i)
    if (x % i == 0) return false;
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  if (prime(n))
    cout << 1;
  else if (prime(n - 2))
    cout << 2;
  else if (n % 2 == 0)
    cout << 2;
  else
    cout << 3;
}
