#include <bits/stdc++.h>
using namespace std;
template <typename T>
T Abs(T first) {
  return (first < 0 ? -first : first);
}
template <typename T>
T Sqr(T first) {
  return (first * first);
}
string plural(string s) {
  return (int((s).size()) && s[int((s).size()) - 1] == 'x' ? s + "en"
                                                           : s + "s");
}
const int INF = (int)1e9;
const long double EPS = 1e-12;
const long double PI = acos(-1.0);
bool Read(int &first) {
  char c, r = 0, n = 0;
  first = 0;
  for (;;) {
    c = getchar();
    if ((c < 0) && (!r)) return (0);
    if ((c == '-') && (!r))
      n = 1;
    else if ((c >= '0') && (c <= '9'))
      first = first * 10 + c - '0', r = 1;
    else if (r)
      break;
  }
  if (n) first = -first;
  return (1);
}
bool P(int v) {
  int s = sqrt((long double)v) + EPS;
  int i;
  for (i = 2; i <= s; i++)
    if (v % i == 0) return (0);
  return (1);
}
int main() {
  if (0) freopen("in.txt", "r", stdin);
  int v;
  int ans;
  Read(v);
  if (P(v))
    ans = 1;
  else if (v % 2 == 0)
    ans = 2;
  else if (P(v - 2))
    ans = 2;
  else
    ans = 3;
  printf("%d\n", ans);
  return (0);
}
