#include using namespace std; int N, dp[40030]; bool prime[20010]; int main(){ for(int i=0;i<40030;i++){ dp[i]=-1; } for(int i=0;i<20010;i++){ prime[i]=true; } prime[1]=true; for(int i=2;i<=sqrt(20010);i++){ if(!prime[i]){ continue; } for(int j=i+i;j<20010;j+=i){ prime[j]=false; } } cin>>N; dp[0]=0; for(int p=2;p<20010;p++){ if(!prime[p]){ continue; } for(int i=20010;i>=0;i--){ if(p+i<=N&&dp[i]!=(-1)){ dp[i+p]=max(dp[i+p], dp[i]+1); } } } cout<