#include <bits/stdc++.h>
using namespace std;
long long bp(long long a, long long b, long long mod) {
  if (b == 0) return 1;
  if (b % 2)
    return (bp((a * a) % mod, b / 2, mod) * a) % mod;
  else
    return bp((a * a) % mod, b / 2, mod);
}
int main() {
  long long n;
  cin >> n;
  int fl = 0;
  int fl2 = 0;
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) fl = 1;
  for (long long i = 2; i * i <= n - 2; i++)
    if ((n - 2) % i == 0) fl2 = 1;
  if (fl == 0)
    cout << 1;
  else if (n % 2 == 0)
    cout << 2;
  else if (fl2 == 0)
    cout << 2;
  else
    cout << 3;
  return 0;
}
