#include<bits/stdc++.h>

using namespace std;

int n,t,ans=0,a[1000010];

bool check(int s){

if(s<2)return 0;

for(int i=2;i<=sqrt(s);i++){

    if(s%i==0)return 0;
}


return 1;

}

void d(int now,int sum,int cnt){

if(now==t+1){

    if(sum==n)ans=max(ans,cnt);
    
    return;
}


d(now+1,sum,cnt);

if(sum+a[now]<=n)

d(now+1,sum+a[now],cnt+1);

}

int main(){

cin>>n;

int l=0;

for(int i=2;i<=n;i++){

    if(check(i))l++,a[l]=i,t++;
}


d(1,0,0);

cout<<ans;

return 0;

}