#include <bits/stdc++.h>
using namespace std;
bool Prime(int x) {
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
int main() {
  int n, ans = 0;
  cin >> n;
  int fans;
  if (n & 1)
    fans = 3;
  else
    fans = 2;
  for (; n;) {
    int j = n;
    for (; !Prime(j) || (n - j) == 1; j--)
      ;
    ans++;
    n -= j;
  }
  cout << min(fans, ans) << endl;
}
