#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n, i;
  scanf("%I64d", &n);
  if (n <= 3) {
    printf("1");
    return 0;
  }
  if (n == 4) {
    printf("2");
    return 0;
  }
  if (n % 2 == 0)
    printf("2");
  else {
    bool u = 1;
    for (i = 2; i * i <= n; i++)
      if (n % i == 0) {
        u = 0;
        break;
      }
    if (u)
      printf("1");
    else {
      n = n - 2;
      bool v = 1;
      for (i = 2; i * i <= n; i++)
        if (n % i == 0) {
          v = 0;
          break;
        }
      if (v)
        printf("2");
      else
        printf("3");
    }
  }
}
