#include #define rep(i,n) for(int i = 0; i < (n); ++i) #define rrep(i,n) for(int i = 1; i <= (n); ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) #define srep(i,s,t) for (int i = s; i < t; ++i) using namespace std; typedef long long int ll; typedef pair P; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector

vp; #define dame { puts("-1"); return 0;} #define yn {puts("Yes");}else{puts("No");} /* Max_Prime以下の素数をprimes[]に格納 */ const int Max_Prime = 21000; int tmp_primes[Max_Prime]; vector primes; void PrimeInit() { rep(i,Max_Prime)tmp_primes[i] = 1; tmp_primes[0] = 0; tmp_primes[1] = 0; rep(i,Max_Prime){ if(tmp_primes[i] == 0)continue; int j = 2; while(i * j <= Max_Prime){ tmp_primes[i*j] = 0; j++; } } rep(i,Max_Prime){ if(tmp_primes[i])primes.push_back(i); } } int main(){ PrimeInit(); int dp[21000] = {}; int i = 0; while(primes[i] <= 20000){ int x = primes[i]; int dp2[21000] = {}; rep(j,21000)dp2[j] = dp[j]; srep(j,x,20001){ if(j == x){ dp2[j] = max(dp[j], 1); }else if(dp[j-x]){ dp2[j] = max(dp[j], dp[j-x]+1); } } rep(j,21000)dp[j] = dp2[j]; i++; } int n; cin >> n; if(dp[n] == 0)dp[n] = -1; cout << dp[n] << endl; return 0; }