#include <bits/stdc++.h>
using namespace std;
int n;
bool isp(int n) {
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
void get_input() { cin >> n; }
void solve() {
  if (isp(n)) {
    cout << 1 << '\n';
  } else if (n % 2 == 0 || isp(n - 2) || isp(n - 3)) {
    cout << 2 << '\n';
  } else
    cout << 3 << '\n';
}
void output() {}
int main() {
  ios_base ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tc = 1;
  while (tc--) {
    get_input(), solve(), output();
  }
  return 0;
}
