#include<bits/stdc++.h>
using namespace std;
int n,f[1005],zhi[1005];
void prime()
{
	for(int i=2;i<=n;i++)
	{
		if(zhi[i]==0)
		{
			for(int j=2;j<=n/i;j++)
			{
				zhi[i*j]=1;
			}	
		}
			
		
	}
}
int main()
{
	cin>>n;
	prime();
	f[1]=0;
	f[2]=1;
	f[3]=1;
	for(int i=4;i<=n;i++)
	{
		for(int j=1;j<i-1;j++)
		{
			if(zhi[j]==0&&zhi[i-j]==0)
			{
				f[i]=f[j]+f[i-j];
				
				break;
			}
		}
		if(zhi[i]==0)f[i]++;
		
	}
	cout<<f[n];
}