#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.sync_with_stdio(false);
  cin.tie(nullptr);
  long long int n;
  cin >> n;
  bool prime = true;
  for (long long int i = 2; i < n && i < 101010; ++i) {
    if (n % i == 0) {
      prime = false;
    }
  }
  if (prime) {
    cout << "1\n";
    return 0;
  }
  if (n % 2 == 0) {
    cout << "2\n";
    return 0;
  }
  bool prime2 = true;
  long long int n2 = n - 2;
  for (long long int i = 2; i < n2 && i < 101010; ++i) {
    if (n2 % i == 0) {
      prime2 = false;
    }
  }
  if (prime2) {
    cout << "2\n";
    return 0;
  }
  cout << "3\n";
  return 0;
}
