#include <bits/stdc++.h>
const int oo = 0x3f3f3f3f;
template <typename T>
inline bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
template <typename T>
inline bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
std::string procStatus() {
  std::ifstream t("/proc/self/status");
  return std::string(std::istreambuf_iterator<char>(t),
                     std::istreambuf_iterator<char>());
}
template <typename T>
T read(T &first) {
  int f = 1;
  char ch = getchar_unlocked();
  for (; !isdigit(ch); ch = getchar_unlocked())
    if (ch == '-') f = -1;
  for (first = 0; isdigit(ch); ch = getchar_unlocked())
    first = 10 * first + ch - '0';
  return first *= f;
}
template <typename T>
void write(T first) {
  if (first == 0) {
    putchar_unlocked('0');
    return;
  }
  if (first < 0) {
    putchar_unlocked('-');
    first = -first;
  }
  static char s[20];
  int top = 0;
  for (; first; first /= 10) s[++top] = first % 10 + '0';
  while (top) putchar_unlocked(s[top--]);
}
bool isprime(long long first) {
  if (first == 2) return true;
  if ((first & 1) == 0) return false;
  for (long long i = 2; i * i <= first; ++i) {
    if (first % i == 0) return false;
  }
  return true;
}
int main() {
  long long N;
  read(N);
  if (isprime(N))
    puts("1");
  else if ((N & 1) == 0 || (N > 2 && isprime(N - 2)))
    puts("2");
  else
    puts("3");
  return 0;
}
