#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
void extendgcd(long long a, long long b, long long* v) {
  if (b == 0) {
    v[0] = 1;
    v[1] = 0;
    v[2] = a;
    return;
  }
  extendgcd(b, a % b, v);
  long long x = v[1];
  v[1] = v[0] - v[1] * (a / b);
  v[0] = x;
  return;
}
long long gcd(long long a, long long b) {
  if (b > a) {
    return gcd(b, a);
  }
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
vector<long long> sieve(int n) {
  int* arr = new int[n + 1]();
  vector<long long> vect;
  for (int i = 2; i * i <= n; i++)
    if (arr[i] == 0) {
      for (int j = 2 * i; j <= n; j += i) arr[j] = 1;
    }
  for (int i = 2; i <= n; i++) {
    if (arr[i] == 0) vect.push_back(i);
  }
  return vect;
}
long long phit(long long n) {
  vector<long long> vect(n);
  vect[0] = 0, vect[1] = 1;
  for (long long i = 2; i <= n; i++) vect[i] = i;
  for (long long i = 2; i <= n; i++) {
    if (vect[i] == i)
      for (long long j = i; j <= n; j += i) vect[j] -= vect[j] / i;
  }
  return vect[n];
}
long long mod_add(long long a, long long b, long long m) {
  a = a % m;
  b = b % m;
  return (((a + b) % m) + m) % m;
}
long long mod_mul(long long a, long long b, long long m) {
  a = a % m;
  b = b % m;
  return (((a * b) % m) + m) % m;
}
long long mod_sub(long long a, long long b, long long m) {
  a = a % m;
  b = b % m;
  return (((a - b) % m) + m) % m;
}
long long invmod(long long a, long long m, long long mo) {
  long long res = 1;
  while (m) {
    if (m & 1) res = mod_mul(a, res, mo);
    a = mod_mul(a, a, mo);
    m >>= 1;
  }
  return res;
}
void _print(long long t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(double t) { cerr << t; }
template <class T, class V>
void _print(map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(unordered_map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(unordered_set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(unordered_multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(vector<T> v);
template <class T>
void _print(vector<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(pair<T, V> p) {
  cerr << "{";
  _print(p.first);
  cerr << ",";
  _print(p.second);
  cerr << "}";
}
static const int N = 1e5 + 10;
bool isprime(long long n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void solve(int ttc) {
  long long n;
  cin >> n;
  if (isprime(n)) {
    cout << 1 << "\n";
  } else {
    if (n % 2 == 0 or isprime(n - 2)) {
      cout << 2 << "\n";
    } else {
      cout << 3 << "\n";
    }
  }
}
int main() {
  clock_t begin_69 = clock();
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int test_cases = 1;
  for (int ttc = 1; ttc <= test_cases; ttc++) {
    solve(ttc);
  }
}

### Prompt

Your task is to create a CPP solution to the following problem:

Mr. Funt now lives in a country with a very specific tax laws. The total income of mr. Funt during this year is equal to n (n ≥ 2) burles and the amount of tax he has to pay is calculated as the maximum divisor of n (not equal to n, of course). For example, if n = 6 then Funt has to pay 3 burles, while for n = 25 he needs to pay 5 and if n = 2 he pays only 1 burle.

As mr. Funt is a very opportunistic person he wants to cheat a bit. In particular, he wants to split the initial n in several parts n1 + n2 + ... + nk = n (here k is arbitrary, even k = 1 is allowed) and pay the taxes for each part separately. He can't make some part equal to 1 because it will reveal him. So, the condition ni ≥ 2 should hold for all i from 1 to k.

Ostap Bender wonders, how many money Funt has to pay (i.e. minimal) if he chooses and optimal way to split n in parts.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 2·109) — the total year income of mr. Funt.

Output

Print one integer — minimum possible number of burles that mr. Funt has to pay as a tax.

Examples

Input

4


Output

2


Input

27


Output

3

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
void extendgcd(long long a, long long b, long long* v) {
  if (b == 0) {
    v[0] = 1;
    v[1] = 0;
    v[2] = a;
    return;
  }
  extendgcd(b, a % b, v);
  long long x = v[1];
  v[1] = v[0] - v[1] * (a / b);
  v[0] = x;
  return;
}
long long gcd(long long a, long long b) {
  if (b > a) {
    return gcd(b, a);
  }
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
vector<long long> sieve(int n) {
  int* arr = new int[n + 1]();
  vector<long long> vect;
  for (int i = 2; i * i <= n; i++)
    if (arr[i] == 0) {
      for (int j = 2 * i; j <= n; j += i) arr[j] = 1;
    }
  for (int i = 2; i <= n; i++) {
    if (arr[i] == 0) vect.push_back(i);
  }
  return vect;
}
long long phit(long long n) {
  vector<long long> vect(n);
  vect[0] = 0, vect[1] = 1;
  for (long long i = 2; i <= n; i++) vect[i] = i;
  for (long long i = 2; i <= n; i++) {
    if (vect[i] == i)
      for (long long j = i; j <= n; j += i) vect[j] -= vect[j] / i;
  }
  return vect[n];
}
long long mod_add(long long a, long long b, long long m) {
  a = a % m;
  b = b % m;
  return (((a + b) % m) + m) % m;
}
long long mod_mul(long long a, long long b, long long m) {
  a = a % m;
  b = b % m;
  return (((a * b) % m) + m) % m;
}
long long mod_sub(long long a, long long b, long long m) {
  a = a % m;
  b = b % m;
  return (((a - b) % m) + m) % m;
}
long long invmod(long long a, long long m, long long mo) {
  long long res = 1;
  while (m) {
    if (m & 1) res = mod_mul(a, res, mo);
    a = mod_mul(a, a, mo);
    m >>= 1;
  }
  return res;
}
void _print(long long t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(double t) { cerr << t; }
template <class T, class V>
void _print(map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(unordered_map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(unordered_set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(unordered_multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(vector<T> v);
template <class T>
void _print(vector<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(pair<T, V> p) {
  cerr << "{";
  _print(p.first);
  cerr << ",";
  _print(p.second);
  cerr << "}";
}
static const int N = 1e5 + 10;
bool isprime(long long n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void solve(int ttc) {
  long long n;
  cin >> n;
  if (isprime(n)) {
    cout << 1 << "\n";
  } else {
    if (n % 2 == 0 or isprime(n - 2)) {
      cout << 2 << "\n";
    } else {
      cout << 3 << "\n";
    }
  }
}
int main() {
  clock_t begin_69 = clock();
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int test_cases = 1;
  for (int ttc = 1; ttc <= test_cases; ttc++) {
    solve(ttc);
  }
}

```