#include <bits/stdc++.h>
using namespace std;
long long mod_pro(long long x, long long y, long long n) {
  long long ret = 0, tmp = x % n;
  while (y) {
    if (y & 0x1)
      if ((ret += tmp) > n) ret -= n;
    if ((tmp <<= 1) > n) tmp -= n;
    y >>= 1;
  }
  return ret;
}
long long mod(long long a, long long b, long long c) {
  long long ret = 1;
  while (b) {
    if (b & 0x1) ret = mod_pro(ret, a, c);
    a = mod_pro(a, a, c);
    b >>= 1;
  }
  return ret;
}
long long ran() {
  long long ret = rand();
  return ret * rand();
}
bool is_prime(long long n, int t) {
  if (n < 2) return false;
  if (n == 2) return true;
  if (!(n & 0x1)) return false;
  long long k = 0, m, a, i;
  for (m = n - 1; !(m & 1); m >>= 1, k++)
    ;
  while (t--) {
    a = mod(ran() % (n - 2) + 2, m, n);
    if (a != 1) {
      for (i = 0; i < k && a != n - 1; i++) a = mod_pro(a, a, n);
      if (i >= k) return false;
    }
  }
  return true;
}
int main() {
  long long data;
  cin >> data;
  if (is_prime(data, 3)) {
    cout << "1\n";
  } else if (data % 2 == 0) {
    cout << "2\n";
  } else if (is_prime(data - 2, 3)) {
    cout << "2\n";
  } else {
    cout << "3\n";
  }
}
