#include <bits/stdc++.h>
int main() {
  long long N;
  std::cin >> N;
  long long i = 0;
  for (i = 2; i * i <= N; ++i) {
    if ((N % i) == 0) break;
  }
  if (i * i > N) {
    std::cout << 1 << std::endl;
    return 0;
  }
  if ((N % 2) == 0) {
    std::cout << 2 << std::endl;
    return 0;
  }
  N -= 2;
  for (i = 2; i * i <= N; ++i) {
    if ((N % i) == 0) break;
  }
  if (i * i > N) {
    std::cout << 2 << std::endl;
    return 0;
  }
  std::cout << 3 << std::endl;
}
