#include <bits/stdc++.h>
using namespace std;
long long m, n;
int main() {
  cin >> m;
  if (m == 2 || m == 3 || m == 5)
    cout << "1\n";
  else if (m % 2 == 0) {
    cout << "2\n";
  } else {
    bool flag = 0;
    for (int i = 2; i <= sqrt(m); i++) {
      if (m % i == 0) {
        flag = 1;
        break;
      }
    }
    if (!flag) {
      cout << "1\n";
      return 0;
    }
    n = m - 2;
    bool check = 0;
    for (int i = 2; i <= sqrt(n); i++) {
      if (n % i == 0) {
        check = 1;
        break;
      }
    }
    if (!check)
      cout << "2\n";
    else
      cout << "3\n";
  }
  return 0;
}
