#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20000;

int N;

int np[MAXN + 1];
vector<int> primes;

int dp[MAXN + 1];

int main() {
  ios::sync_with_stdio(false);
  cin >> N;
  for (int i = 2; i <= N; ++i) {
    if (np[i]) continue;
    primes.emplace_back(i);
    for (int j = i + i; j <= N; j += i) {
      np[j] = 1;
    }
  }
  memset(dp, 0xc0, sizeof(dp));
  dp[0] = 0;
  for (size_t i = 0; i < primes.size(); ++i) {
    for (int j = N; j >= primes[i]; --j) {
      if (dp[j] < dp[j - primes[i]] + 1) {
        dp[j] = dp[j - primes[i]] + 1;
      }
    }
  }
  if (dp[N] < 0) dp[N] = -1;
  cout << dp[N] << endl;
  return 0;
}