#include<iostream>
#include<cmath>
using namespace std;
int num[50];
int n;
int index=0;
int maxtotal=-1;
 
//判断素数
bool sushu(int m)
{
    bool r = true;
    for (int i=2;i<=sqrt(m);i++)
    {
            if (m % i == 0){
				r = false;
				break;            	
			}
    }
    if(m <= 1){
    	   r = false;
	}
    
    return r;
}

 
//k为当前下标，sum为总和，total为使用的数字的个数
void fun(int k,int sum,int total)
{
   if (sum==n)
   {
       if (total>maxtotal)//更新total
       {
           maxtotal=total;
       }
       return;
   }
   if (sum>n||k>=index)//如果sum超过n，或者下标大于素数个数结束
   {
       return;
   }
   fun(k+1,sum+num[k],total+1);
   fun(k+1,sum,total);
}

int main()
{
 
    cin>>n;
 
    for (int i=2;i<=n;i++)
    {
        if (sushu(i))//如果是素数，将其存进num数组
        {
            num[index++]=i;
        }
    }
 
    fun(0,0,0);
    cout<<maxtotal;
    return 0;
}

/**************************************************************
	Problem: 1379
	User: admin
	Language: C++
	Result: Accepted
	Time:92 ms
	Memory:2072 kb
****************************************************************/