思路也就是暴力了一些的dp，表算完了就直接 $O(1)$ 查询，但不知道为啥WA #9，求助各路大佬帮忙看看。

#include<bits/stdc++.h>
using namespace std;
int T,n;
int p=0,pr[200002];
bool num[200002];
void ols(int x)
{
	memset(num,false,sizeof(num));
	num[0]=num[1]=true;
	for(int i=2;i<=x;i++)
	{
		if(num[i]==false)
		{
			p++;
			pr[p]=i;
		}
		for(int j=1;pr[j]<=x/i;j++)
		{
			num[pr[j]*i]=true;
			if(i%pr[j]==0)
			{
				break;
			}
		}
	}
}
int dp[20002];
bool wl[20002];
int main()
{
	cin>>T;
	ols(20000);
	memset(wl,false,sizeof(wl));
	wl[0]=wl[1]=false;//true=win,false=lose
	dp[0]=dp[1]=0;
	for(int i=2;i<=20000;i++)
	{
		for(int j=1;pr[j]<=i;j++)
		{
			if(!wl[i-pr[j]])
			{
				wl[i]=true;
				break;
			}
		}
	}
	for(int i=2;i<=20000;i++)
	{
		if(wl[i])
		{
			dp[i]=0x3f3f3f3f;
		}else{
			dp[i]=0;
		}
		for(int j=1;pr[j]<=i;j++)
		{
			if(wl[i])
			{
				if(!wl[i-pr[j]])
				{
					dp[i]=min(dp[i],dp[i-pr[j]]+1);
				}
			}else{
				if(wl[i-pr[j]])
				{
					dp[i]=max(dp[i],dp[i-pr[j]]+1);
				}
			}
		}
	}
//	for(int i=1;i<=20;i++)
//	{
//		cout<<dp[i]<<" ";
//	}
//	cout<<endl;
	while(T--)
	{
		cin>>n;
		if(!wl[n])
		{
			cout<<"-1\n";
		}else{
			cout<<dp[n]<<endl;
		}
	}
	return 0;
}
/*
8:2 3 5 7
9:2 3 5 7
16:2 3 5 7 11 13

0<=n<=1时结束 

8:8-7=1 end
9:impossible
16:16-7=9 9先手必败，2步结束 
*/