#include <bits/stdc++.h>
using namespace std;
long long a[2000007];
vector<long long> v;
bool sortinrev(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return (a.first > b.first);
}
void seive() {
  for (long long i = 0; i <= 2000000; i++) a[i] = 1;
  a[0] = a[1] = 0;
  for (long long i = 2; i <= 1553; i++) {
    if (a[i] == 1) {
      v.push_back(i);
      for (long long j = 2 * i; j <= 2000000; j += i) a[j] = 0;
    }
  }
  for (long long i = 1554; i <= 2000000; i++) {
    if (a[i] == 1) v.push_back(i);
  }
}
long long palindrome(long long n) {
  long long x;
  string s = to_string(n);
  if (!(s.length() % 2))
    x = s.length() / 2 - 1;
  else
    x = s.length() / 2;
  for (long long i = 0; i <= x; i++) {
    if (s[i] != s[s.length() - 1 - i]) return 0;
  }
  return 1;
}
long long nCr(long long n, long long r) {
  long long ans = 1;
  long long k = 2;
  if (n - r < r)
    k = n - r;
  else
    k = r;
  for (long long i = n; i >= n - k; i--) {
    ans *= i;
    if (ans % k == 0 && k > 1) {
      ans /= k;
      k--;
    }
  }
  while (k > 1) {
    ans /= k;
    k--;
  }
  return ans;
}
long long fpow(long long a, long long n) {
  if (n == 1) return a;
  if (n % 2) return (a % 1000000007 * fpow(a, n - 1) % 1000000007) % 1000000007;
  return (fpow(a, n / 2) % 1000000007 * fpow(a, n / 2) % 1000000007) %
         1000000007;
}
int32_t main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  long long n;
  cin >> n;
  long long k = 0;
  for (long long i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) {
      k = 1;
      goto x;
    }
  }
x:
  if (k == 0)
    cout << "1";
  else {
    if (n % 2 == 0)
      cout << "2";
    else {
      k = 0;
      for (long long i = 2; i <= sqrt(n - 2); i++) {
        if ((n - 2) % i == 0) {
          k = 1;
          goto y;
        }
      }
    y:
      if (k == 1)
        cout << "3";
      else
        cout << "2";
    }
  }
  return 0;
}
