#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
const long long inf = 1LL << 62;
const long long mx = 100005;
const double eps = 1e-10;
long long dx[10] = {1, 0, -1, 0};
long long dy[10] = {0, -1, 0, 1};
long long power(long long a, long long b) {
  if (b == 0) return 1;
  long long x = power(a, b / 2);
  x = x * x;
  if (b % 2) x = x * a;
  return x;
}
long long bigmod(long long a, long long b) {
  if (b == 0) return 1;
  long long x = bigmod(a, b / 2) % mod;
  x = (x * x) % mod;
  if (b % 2) x = (x * a) % mod;
  return x;
}
long long Set(long long N, long long pos) { return N = N | (1LL << pos); }
long long reset(long long N, long long pos) { return N = N & ~(1LL << pos); }
bool check(long long N, long long pos) { return (bool)(N & (1LL << pos)); }
bool mark[mx];
vector<long long> prime;
void sieve(long long n) {
  mark[1] = 1;
  for (long long i = 4; i <= n; i += 2) mark[i] = 1;
  prime.push_back(2);
  for (long long i = 3; i <= n; i += 2) {
    if (mark[i] == 0) {
      prime.push_back(i);
      if (i * i <= n) {
        for (long long j = i * i; j <= n; j += i * 2) mark[j] = 1;
      }
    }
  }
}
int main() {
  long long tst, a, b, c, k, n, m, res = 0, ans = 0, t = 0;
  sieve(100000);
  scanf("%lld", &n);
  for (long long i = 0;
       i < (long long)(prime).size() and prime[i] * prime[i] <= n; i++) {
    if (n % prime[i] == 0) {
      res = 1;
      break;
    }
  }
  if (!res) {
    cout << 1 << "\n";
    return 0;
  }
  if (n % 2 == 0) {
    cout << 2 << "\n";
  } else {
    n -= 2;
    res = 0;
    for (long long i = 0;
         i < (long long)(prime).size() and prime[i] * prime[i] <= n; i++) {
      if (n % prime[i] == 0) {
        res = 1;
        break;
      }
    }
    if (!res) {
      cout << 2 << "\n";
    } else
      cout << 3 << "\n";
  }
  return 0;
}
