记录编号	362059	评测结果	AAAAAAAAAA
题目名称	质数取石子	最终得分	100
用户昵称	核糖核酸	是否通过	通过
代码语言	C++	运行时间	1.515 s
提交时间	2017-01-06 11:04:34	内存使用	0.49 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 20005
using namespace std;
bool p[N];
int prime[2300], tot = 0;
int T, n, SG[N], pre[N];
bool vis[N];

void Build_prime(int n) {
	memset(p, true, sizeof(p));
	for(int i=2; i<=n; i++)
		if(p[i])
			for(int j=i+i; j<=n; j+=i)
				p[j] = false;
	for(int i=2; i<=n; i++)
		if(p[i]) prime[++tot] = i;
}

void Build_SG(int n) {
	memset(SG, 0, sizeof(SG));
	for(int i=2; i<=n; i++) {
		for(int j=1; j<=tot && prime[j]<=i; j++)
			vis[SG[i-prime[j]]] = true;
		for(int j=0; j<=n; j++)
			if( !vis[j]) { SG[i] = j; break; }
		for(int j=1; j<=tot && prime[j]<=i; j++)
			vis[SG[i-prime[j]]] = false;
	}
}

void Build_pre(int n) {
	pre[0] = pre[1] = 0;
	for(int i=2; i<=n; i++) {
		if(SG[i]) {
			pre[i] = 1000000000;
			for(int j=1; j<=tot && prime[j]<=i; j++)
				if(SG[i-prime[j]] == 0)
					pre[i] = min(pre[i], pre[i-prime[j]]+1);
		}
		else {
			pre[i] = 0;
			for(int j=1; j<=tot && prime[j]<=i; j++)
				pre[i] = max(pre[i], pre[i-prime[j]]+1);
		}
	}
}

int main() {
	freopen("stonegame.in", "r", stdin);
	freopen("stonegame.out", "w", stdout);
	
	Build_prime(20000);
	Build_SG(20000);
	Build_pre(20000);
	
/*	for(int i=0; i<=20000; i++)
		printf("ST[%d] = %d  pre[%d] = %d\n", i, SG[i], i, pre[i]);
	*/
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		printf("%d\n", SG[n] ? pre[n] : -1);
	}
	
	return 0;
}