#include <bits/stdc++.h>
using namespace std;
long long int power(long long int x, long long int y) {
  if (y == 0)
    return 1;
  else if (y % 2 == 0)
    return power(x, y / 2) * power(x, y / 2);
  else
    return x * power(x, y / 2) * power(x, y / 2);
}
long long int binsearch(long long int a[], long long int n, long long int x) {
  long long int low = 1;
  long long int high = n;
  long long int ans;
  while (low <= high) {
    long long int mid = (low + high) / 2;
    if (a[mid] == x)
      return mid;
    else if (a[mid] > x) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int n;
  cin >> n;
  long long int i, c = 0;
  for (i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      c = 1;
      break;
    }
  }
  if (c == 0)
    cout << 1 << endl;
  else {
    if (n % 2 == 0)
      cout << 2 << endl;
    else {
      n -= 2, c = 0;
      for (i = 2; i * i <= n; i++) {
        if (n % i == 0) {
          c = 1;
          break;
        }
      }
      if (c == 0)
        cout << 2 << endl;
      else
        cout << 3 << endl;
    }
  }
}
