#include <bits/stdc++.h>
using namespace std;
unsigned int n;
unsigned int check(unsigned int nr) {
  int x = sqrt(nr);
  for (unsigned int i = 2; i <= x; i++)
    if (nr % i == 0) return nr / i;
  return -1;
}
void solve() {
  unsigned int d[9] = {0, 0, 1, 1, 2, 1, 2, 1, 2};
  int sol = 0;
  while (n > 8) {
    unsigned int val = check(n);
    if (val == -1) {
      sol += 1;
      n = 0;
    } else {
      unsigned int y;
      for (y = n - 2; check(y) != -1; y--)
        ;
      sol += 1;
      n = n - y;
    }
  }
  sol += d[n];
  cout << sol;
}
int main() {
  cin >> n;
  if (check(n) == -1)
    cout << 1;
  else if (n % 2 == 0)
    cout << 2;
  else if (check(n - 2) == -1)
    cout << 2;
  else
    cout << 3;
  return 0;
}
