#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 20007;
const int inf=1e18;
int n,f[N],pr[N],tot=0;
bool vis[N];
signed main(){
	cin >> n;
	vis[0]=vis[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i])pr[++tot]=i;
		for(int j=1;j<=tot&&pr[j]*i<=n;j++){
			vis[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
	for(int i=1;i<=n;i++)f[i]=-inf;
    for(int i=1;i<=tot;i++)
        for (int j=n;j>= 0;j--) 
            if (pr[i]+j<=n)f[pr[i]+j]=max(f[pr[i]+j],f[j]+1);
    cout<<(f[n]<0?-1:f[n]);
}