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

void solve() {
        int N;
        cin >> N;
        vector<int> primes;
        for (int i = 2; i <= N; i++) {
                int cnt = 0;
                for (int j = 1; j <= i; j++) {
                        if (i % j == 0) {
                                cnt++;
                        }
                }
                if (cnt == 2) {
                        primes.push_back(i);
                }
        }
        vector<int> dp(N + 1, -1);
        dp[0] = 0;
        for (auto &prime : primes) {
                for (int i = N; i >= prime; i--) {
                        if (i - prime >= 0 && dp[i - prime] != -1) {
                                dp[i] = max(dp[i], dp[i - prime] + 1);
                        }
                }
        }
        cout << dp[N] << '\n';
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);

        int t = 1;
        // cin >> t;
        while (t--) solve();

        return 0;
}