#include using namespace std; #define int long long using ll=long long; using vi=vector; using vl=vector; using pii=pair; using pll=pair; #define ITR(i,c) for(auto i=begin(c);i!=end(c);++i) #define FORE(x,c) for(auto &x:c) #define FOR(i,a,n) for(int i=a,i##_len=(int)n;i=0;--i) #define ALL(c) begin(c),end(c) #define RALL(c) rbegin(c),rend(c) #define SZ(c) ((int)c.size()) #define dump(...) const int DX[9]={0,1,0,-1,1,1,-1,-1,0}, DY[9]={-1,0,1,0,-1,1,1,-1,0}; const int INF=1e9*2; const long long INFLL=1e18*2; template ostream& operator << (ostream &os, const vector &v) { ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; } template istream& operator >> (istream &is, vector &v) { ITR(i,v) is >> * i; return is; } template istream& operator >> (istream &is, pair &p) { is >> p.second >> p.first; return is; } templatebool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b isPrime; void eratosthenes(int N) { isPrime.resize(N+1); fill(ALL(isPrime),true); FOR(i,2,sqrt(N)+1) if(isPrime[i]) for(int j=2; i*j<=N; j++) isPrime[i*j]=false; } vector getPrime(int N) { eratosthenes(N); vector prime; FOR(i,2,N+1) if(isPrime[i]) prime.push_back(i); return prime; } int dp[2270][20010]; signed main() { cin.tie(0); ios::sync_with_stdio(false); REP(i,2270) REP(j,20010) dp[i][j]=-1; vi p=getPrime(20010); int N,ans=-1; cin>>N; dp[0][0]=0; dp[0][p[0]]=1; FOR(i,0,SZ(p)-1) { REP(j,N+1) { if(dp[i][j]==-1) continue; if(chmax(dp[i+1][j],dp[i][j])) { if(j==N) ans=dp[i+1][j]; } if(j+p[i+1]>N) continue; if(chmax(dp[i+1][j+p[i+1]],dp[i][j]+1)) { if(j==N) ans=dp[i+1][j+p[i+1]]; } } } cout<<(ans==-1?-1:ans)<