dp[1][i]:
DD选择的时候，剩余i石子，DD赢的最小步数。若此时DD是必败态，则为-1；
dp[2][i]:
MM选择的时候，剩余i石子，MM输的最大步数。若此时DD是必胜态，则为-1；
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
#define maxn 20050
int prime[maxn];
int isprime[maxn];
int nearprime[maxn];
int numprime;
int dp[3][maxn];
void dos()
{prime[0]=0;prime[1]=0;prime[2]=1;for(int i=3;i<maxn;i++)prime[i]=i%2;for(int i=2;i<sqrt(maxn);i++){if(prime[i]==0)continue;for(int j=2;j*i<maxn;j++){prime[j*i]=0;}}numprime=0;for(int i=0;i<maxn;i++){if(prime[i])isprime[numprime++]=i;nearprime[i]=numprime-1;}
}
int pan(int people,int n)
{int i;if(dp[people][n]!=-2)return dp[people][n];if(people==1){int leap=0;dp[1][n]=9999999;if(prime[n]||prime[n-1]){dp[1][n]=1;return 1;}for(i=0;i<=nearprime[n];i++){if(pan(2,n-isprime[i])>-1){dp[1][n]=min(dp[1][n],dp[2][n-isprime[i]]+1);leap=1;}}if(leap==0)dp[1][n]=-1;}else if(people==2){dp[2][n]=0;if(prime[n]||prime[n-1]){dp[2][n]=-1;return -1;}for(i=0;i<=nearprime[n];i++){if(pan(1,n-isprime[i])==-1){dp[2][n]=-1;break;}else{dp[2][n]=max(dp[1][n-isprime[i]]+1,dp[2][n]);}}}return dp[people][n];
}
void play()
{dos();int i;for(i=0;i<maxn;i++)dp[1][i]=dp[2][i]=-2;dp[1][0]=-1;dp[1][1]=-1;dp[1][2]=1;dp[2][0]=0;dp[2][1]=0;dp[2][2]=-1;for(i=3;i<maxn;i++){dp[1][i]=pan(1,i);}
}
int main()
{int n,m;play();scanf("%d",&n);while(n--){scanf("%d",&m);printf("%d\n",dp[1][m]);}return 0;
}