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

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

    vector<bool> prime(N,true);
    prime.at(0) = false; prime.at(1) = false;
    for(int i = 0; i < N; i++){
        if(!prime.at(i)) continue;
        for(int j = i*2; j < N; j+=i) prime.at(j) = false;
    }

    vector<int> prime2;
    for(int i = 0; i < N; i++){
        if(prime.at(i)) prime2.push_back(i);
    }

    vector<vector<long long>> dp(prime2.size()+1, vector<long long>(N+1, -N*N));
    dp.at(0).at(0) = 0;
    for(int i = 0; i < prime2.size(); i++){
        for(int j = 0; j <= N; j++){
            if(j - prime2.at(i) >= 0) dp.at(i+1).at(j) = max(dp.at(i).at(j-prime2.at(i)) + 1, dp.at(i+1).at(j));
            dp.at(i+1).at(j) = max(dp.at(i).at(j), dp.at(i+1).at(j));
        }
    }

    if(dp.at(prime2.size()).at(N) < 0) cout << -1 << endl;
    else cout << dp.at(prime2.size()).at(N) << endl;



}