#include <bits/stdc++.h>
using namespace std;
long long int a[5000005] = {0};
void num(long long int a[]) {
  for (long long int i = 2; i <= 5000005; i++) {
    if (a[i] == 0) {
      for (long long int j = i; j <= 5000005; j += i) {
        a[j] = a[j / i] + 1;
      }
    }
  }
}
long long int power(long long int x, long long int y, long long int p) {
  long long int ans = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) ans = (ans * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return ans;
}
long long int fact(long long int n) {
  long long int res = 1;
  for (long long int i = 2; i <= n; i++) res = res * i;
  return res;
}
long long int nCr(long long int n, long long int r) {
  return fact(n) / (fact(r) * fact(n - r));
}
int modInverse(long long int n, long long int p) { return power(n, p - 2, p); }
void jai_mata_di() {
  long long int q;
  long long int k1, k2, x1 = 0, x2 = 0, y1 = 0, y2 = 0, n, x, r = 0, g = 0,
                        b = 0, y, i, j, k, cnt = 0, flag = 1, sum = 0, ans = 0,
                        d, mx = -1e13;
  cin >> n;
  for (i = 2; i * i <= n; i++) {
    if (n % i == 0) flag = 0;
  }
  if (flag) {
    cout << 1;
    return;
  }
  if (n % 2 == 0)
    cout << 2;
  else {
    flag = 1;
    for (i = 2; i * i <= (n - 2); i++) {
      if ((n - 2) % i == 0) flag = 0;
    }
    if (flag)
      cout << 2;
    else
      cout << 3;
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int tt = 1.0 * clock();
  int t;
  t = 1;
  for (int y = 0; y < t; y++) {
    jai_mata_di();
    cout << endl;
  }
  return 0;
}
