#include <bits/stdc++.h>
using namespace std;
bool parz(int k) {
  for (int j = 2; j <= sqrt(k); j++) {
    if (k % j == 0) return false;
  }
  return true;
}
int tar, bar, qaar, ter;
int main() {
  int c, d, e, q, i, j, a, b, k, l, m, n1, x, y, v, t;
  double ans = 1000000000;
  string h;
  cin >> n1;
  if (parz(n1))
    cout << 1 << endl;
  else if (n1 % 2 == 0)
    cout << 2 << endl;
  else if (parz(n1 - 2))
    cout << 2 << endl;
  else
    cout << 3 << endl;
  return 0;
}
