#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e5 + 10;
bool isp[maxn];
int _prime[maxn], lp = 0;
int _minCost[maxn];
void InitPrime() {
  isp[0] = isp[1] = true;
  for (int i = 4; i < maxn; i += 2) isp[i] = true;
  for (int i = 3; i * i < maxn; i += 2)
    if (!isp[i])
      for (int j = i * i; j < maxn; j += i) isp[j] = true;
  _prime[lp++] = 2;
  for (int i = 3; i < maxn; i += 2)
    if (!isp[i]) _prime[lp++] = i;
}
bool IsPrime(long long n) {
  if (n < maxn) return !isp[n];
  for (int i = 0; i < lp && (long long)_prime[i] * _prime[i] <= n; ++i) {
    if (n % _prime[i] == 0) return false;
  }
  return true;
}
int minCost(long long n) {
  if (IsPrime(n)) return 1;
  for (int i = 0; i < lp && _prime[i] + 2 <= n; ++i) {
    if (n - _prime[i] >= 2 && IsPrime(n - _prime[i])) return 2;
  }
  return 3;
}
int main() {
  InitPrime();
  long long n;
  cin >> n;
  cout << minCost(n) << endl;
  return 0;
}
