#include <bits/stdc++.h>
using namespace std;
const int dr[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dc[] = {0, 1, 0, -1, 1, -1, -1, 1};
const double eps = 1e-9;
const int INF = 0x7FFFFFFF;
const long long INFLL = 0x7FFFFFFFFFFFFFFFLL;
const double pi = acos(-1);
template <class T>
T take(queue<T> &O) {
  T tmp = O.front();
  O.pop();
  return tmp;
}
template <class T>
T take(stack<T> &O) {
  T tmp = O.top();
  O.pop();
  return tmp;
}
template <class T>
T take(priority_queue<T> &O) {
  T tmp = O.top();
  O.pop();
  return tmp;
}
template <class T>
inline void getint(T &num) {
  bool neg = 0;
  num = 0;
  char c;
  while ((c = getchar_unlocked()) && (!isdigit(c) && c != '-'))
    ;
  if (c == '-') {
    neg = 1;
    c = getchar_unlocked();
  }
  do num = num * 10 + c - '0';
  while ((c = getchar_unlocked()) && isdigit(c));
  if (neg) num = -num;
}
template <class T>
inline bool inRange(T z, T a, T b) {
  return a <= z && z <= b;
}
void OPEN(string in = "input.txt", string out = "output.txt") {
  freopen(in.c_str(), "r", stdin);
  freopen(out.c_str(), "w", stdout);
  return;
}
long long n;
long long ans;
inline bool isprime(long long x) {
  if (x == 2) return 1;
  if (x < 2) return 0;
  if ((x & 1) == 0) return 0;
  for (long long i = 3; i * i <= x; i += 2) {
    if (x % i == 0) return 0;
  }
  return 1;
}
int main(int argc, char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  if (n == 2 || isprime(n))
    ans = 1;
  else if (n > 2) {
    if ((n & 1) == 0)
      ans = 2;
    else if (isprime(n - 2))
      ans = 2;
    else
      ans = 3;
  }
  cout << ans << "\n";
}
