#include <bits/stdc++.h>

using namespace std;

bool is_prime[20010];
vector<int> prime;
vector< vector<int> > dp;

void sieve(int n) {
  fill(is_prime, is_prime + n, true);
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i < n; i++) {
    if (!is_prime[i]) continue;
    prime.push_back(i);
    for (int j = 2 * i; j < n; j += i) {
      is_prime[j] = false;
    }
  }
}

int main() {
  int n;
  cin >> n;

  sieve(n + 10);
  dp.resize(prime.size() + 1, vector<int>(n + 1, -1));
  dp[0][0] = 0;

  for (int i = 0; i < prime.size(); i++) {
    for (int j = 0; j <= n; j++) {
      if (j - prime[i] < 0) {
        dp[i + 1][j] = dp[i][j];
      } else if (dp[i][j - prime[i]] >= 0) {
        dp[i + 1][j] = max(dp[i][j], dp[i][j - prime[i]] + 1);
      } else {
        dp[i + 1][j] = dp[i][j];
      }
    }
  }
  cout << dp[prime.size()][n] << endl;

  return 0;
}