#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<class t> using vc = vector<t>;
template<class t> using vvc = vc<vc<t>>;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using vi = vc<int>;
using vvi = vvc<int>;
using vl = vc<ll>;
using vvl = vvc<ll>;

#define rep(i,a,b) for (int i = (int)(a); i < (int)(b); i++)
#define irep(i,a,b) for (int i = (int)(a); i > (int)(b); i--)
#define all(a) a.begin(),a.end()
#define print(n) cout << n << '\n'
#define pritn(n) print(n)
#define printv(n,a) {copy(all(n),ostream_iterator<a>(cout," ")); cout<<"\n";}
#define printvv(n,a) {for(auto itr:n) printv(itr,a);}
#define rup(a,b) (a+b-1)/b
#define input(A,N) rep(i,0,N) cin>>A[i]
#define chmax(a,b) a = max(a,b)
#define chmin(a,b) a = min(a,b)
ll gcd(ll n, ll m){
    if (m > n) swap(n,m);
    if (m == 0) return n;
    return gcd(m,n%m);
}

ll ksc(ll x,ll y,ll p){
	ll t=0; for (; y; y>>=1,x=(x<<1)%p) if (y&1) t=(t+x)%p;
	return t;
}
ll ksm(ll x,ll y,ll p){
	ll t=1; for (; y; y>>=1,x=ksc(x,x,p)) if (y&1) t=ksc(t,x,p);
	return t;
}
bool isprm(ll x){
	if (x==2) return 1; if (x==1 || !(x&1)) return 0;
	ll t=x-1; int len=0,i,j;
	for (; !(t&1); t>>=1) len++;
	for (i=1; i<=10; i++){
		ll k=ksm(rand()%(x-1)+1,t,x);
		for (j=1; j<=len; j++,k=ksc(k,k,x))
			if (j<len-1 && ksc(k,k,x)==1 && k!=1 && k!=x-1) return 0;
		if (k!=1) return 0;
	}
	return 1;
}

ll pho(ll x){
	ll u=rand()%(x-1)+1,v=u,w,t=1; int i=2,k=2;
	while (!w || w==2) w=rand()%(x-1)+1;
	for (; t==1; i++){
		if (i==k){ v=u; k<<=1; }
		u=(ksc(u,u,x)+x-w)%x;
		t=gcd(v-u+x,x);
	}
	return t;
}

int main(){
    cout << fixed << setprecision(15);
    
    int n;
    cin>>n;
    vi dp(n+1,0);
    for(int i = 2;i<=n;i++){
        if(!isprm(i)) continue;
        for(int j = n;j>=0;j--){
            int ni = j - i;
            if(ni<0) continue;
            if(dp[ni]==0) continue;
            chmax(dp[j],dp[ni]+1);
        }
        chmax(dp[i],1);
    }
    if(dp[n]==0) print(-1);
    else print(dp[n]);
    //printv(dp,int);
    //system("pause");
    return 0;
}