#include <bits/stdc++.h>
using namespace std;
inline char get(void) {
  static char buf[100000], *S = buf, *T = buf;
  if (S == T) {
    T = (S = buf) + fread(buf, 1, 100000, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
inline void read(int &x) {
  static char c;
  x = 0;
  for (c = get(); c < '0' || c > '9'; c = get())
    ;
  for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
}
const int N = 501010;
const int INF = 1 << 30;
long long n, cnt, m;
long long f[N];
inline long long Min(long long a, long long b) { return a < b ? a : b; }
int main(void) {
  cin >> n;
  if (n <= 2)
    cout << 1 << endl;
  else if (n <= 7) {
    if (n & 1)
      cout << 1 << endl;
    else
      cout << 2 << endl;
  } else {
    if (n & 1) {
      bool f = 1;
      m = sqrt(n);
      for (int i = 2; i <= m; i++)
        if (n % i == 0) {
          f = 0;
          break;
        }
      if (f) {
        cout << 1 << endl;
        return 0;
      }
      m = sqrt(n) + 1;
      n -= 2;
      f = 1;
      for (int i = 2; i <= m; i++)
        if (n % i == 0) {
          f = 0;
          break;
        }
      if (f)
        cout << 2 << endl;
      else
        cout << 3 << endl;
    } else
      cout << 2 << endl;
  }
  return 0;
}
