#include #include #include #include #include #include #include #include #include #define int long long int #define rep(i, n) for(int i = 0; i < (n); ++i) using namespace std; typedef pair P; const int INF = 1e15; const int MOD = 1e9+7; vector prime(int n){ vector t; vector x(n+1, true); t.push_back(2); int i; for(i = 3; i * i <= n; i += 2){ if(!x[i]){ continue; } t.push_back(i); for(int j = i; j <= n; j += i){ x[j] = false; } } for(; i <= n; i += 2){ if(x[i]){ t.push_back(i); } } return t; } signed main(){ int n; cin >> n; vector p = prime(n); vector sp((int)p.size()); sp[0] = 2; for(int i = 1; i < (int)p.size(); i++){ sp[i] = sp[i-1] + p[i]; } vector dp(n+1); rep(i, (int)p.size()){ dp[p[i]] = 1; } rep(i, (int)p.size()){ for(int j = n; j >= 0; j--){ if(j <= sp[i] + p[i] || dp[j-p[i]] == 0){ continue; } dp[j] = max(dp[j], dp[j-p[i]]+1); } } if(dp[n] > 0){ cout << dp[n] << endl; }else{ cout << -1 << endl; } return 0; }