#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) typedef long long ll; int memo[10001]; int pr[10001]; int vpr[10001]; int PSIZE; int solve(int curr) { if(curr <= 1) { return 0; } int& ret = memo[curr]; if(ret >= 0) { return ret; } ret = 0; for(int i=0; i curr) { break; } ret |= !solve(curr - vpr[i]); } return ret; } int main() { memset(memo, -1, sizeof memo); int N;cin >> N; fill(pr, pr+N+1, 1); pr[0] = pr[1] = 0; for(int i=2; (ll)i*i < N+1; i++) if(pr[i]) for(int j=i*i; j<=N+1; j+=i) pr[j] = 0; for(int i=0; i