#include <bits/stdc++.h>
using namespace std;
vector<bool> Eratosthenes(int n){
    vector<bool> isPrime(n+1,true);
    isPrime[0] = false;
    isPrime[1] = false;
    for(int p = 2; p*p <= n; p++){
        if(isPrime[p]){
            for(int q = p*2; q <= n; q+=p){
                isPrime[q] = false;
            }
        }
    }
    return isPrime;
}
int main(){
    int n;
    cin >> n;
    vector<bool> isPrime = Eratosthenes(n);
    vector<int> Prime;
    vector<int> dp(n+1,-1);//合計がiになるときの和の回数の最大値
    for(int i = 0; i <= n; i++){
        if(isPrime[i]){
            Prime.push_back(i);
        }
    }
    dp[0] = 0;
    for(auto p : Prime){
        for(int i = n; i >= 0; i--){
            if(p+i <= n && dp[i] != -1){
                dp[p+i] = max(dp[p+i],dp[i] + 1);
            }
        }
    }
    cout << dp[n] << endl;
    
}