#include <bits/stdc++.h>
using namespace std;
bool prost(long long int ch) {
  short k = 0;
  for (long long int i = 2; i <= sqrt(ch) && k == 0; ++i)
    if (ch % i == 0) ++k;
  return (k == 0);
}
int main() {
  long long int i, n, s;
  cin >> n;
  if (prost(n))
    s = 1;
  else if ((n % 2 == 0) || (prost(n - 2)))
    s = 2;
  else
    s = 3;
  cout << s;
  return 0;
}
