#include #define PN 2270 using namespace std; int N, PC = 0; int prime[PN] = {0}; bool used[PN] = {false}; int dp[20001] = {0}; int result = 0; void rec(int count = 0, int sum = 0){ if(sum > N) return; if(sum == N){ if(result < count) result = count; return; } if(dp[sum] != 0 && dp[sum] > count) return; dp[sum] = count; int i; for(i = 0; i < PC; ++i){ if(!used[i]){ used[i] = true; rec(count + 1, sum + prime[i]); used[i] = false; } } return; } int main(void){ cin >> N; int i, j, k; prime[PC++] = 2; for(i = 3; i <= N; i += 2){ k = 0; for(j = 3; j <= sqrt(i); j += 2){ if(i % j == 0){ k = 1; break; } } if(k == 0) prime[PC++] = i; } rec(); if(result) cout << result << endl; else cout << -1 << endl; return 0; }