#include <bits/stdc++.h>
using namespace std;
template <class A, class B>
ostream &operator<<(ostream &out, const pair<A, B> &a) {
  return out << "(" << a.first << "," << a.second << ")";
}
template <class A>
ostream &operator<<(ostream &out, const vector<A> &a) {
  for (const A &it : a) out << it << " ";
  return out;
}
template <class A, class B>
istream &operator>>(istream &in, pair<A, B> &a) {
  return in >> a.first >> a.second;
}
template <class A>
istream &operator>>(istream &in, vector<A> &a) {
  for (A &i : a) in >> i;
  return in;
}
ifstream cinn("in.txt");
ofstream coutt("out.txt");
long long poww(const long long &a, long long b,
               const long long &m = 1000000007) {
  if (b == 0) return 1;
  long long first = poww(a, b / 2, m);
  first = first * first % m;
  if (b & 1) first = first * a % m;
  return first;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long _sum(long long n) { return (n * (n + 1)) / 2; }
bool isp(long long n) {
  long long i;
  for (i = 2; i * i <= n; i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t, n, h, k, c, a, b, f, f2, t2, t3, m, ans, i, j, mnt, mxt, r, l,
      j1, j2;
  cin >> n;
  if (isp(n)) {
    cout << 1 << '\n';
  } else if (n % 2 == 0) {
    cout << 2 << '\n';
  } else if (n % 2) {
    if (isp(n - 2))
      cout << 2 << '\n';
    else
      cout << 3 << '\n';
  }
}
