#include <bits/stdc++.h>
using namespace std;
const long long max_n = 100112, log_n = 20, max_k = 101111, inf = 1011111111,
                C = 1, V = 2;
const long double eps = 1e-10;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
long long n, p[100], cnt;
int rec(int x, int ind) {
  if (x == 0) return 0;
  int ans = inf;
  for (int i = ind; i < 100; ++i) {
    if (x >= p[i]) {
      ans = min(ans, rec(x - p[i], i));
    }
  }
  return ans + 1;
}
bool is_prime(int x) {
  for (int q = 2; q * q <= x; ++q)
    if (x % q == 0) {
      return false;
    }
  return true;
}
int main() {
  int n;
  cin >> n;
  for (int i = 2; cnt < 100; ++i) {
    if (is_prime(i)) {
      p[cnt++] = i;
    }
  }
  if (is_prime(n)) {
    cout << "1\n";
    return 0;
  }
  if (is_prime(n - 2) || n % 2 == 0) {
    cout << "2\n";
    return 0;
  }
  cout << "3\n";
}
