数据过水

# include <bits/stdc++.h>
using namespace std;
const int N = 2e4;
int vis[N],prim[N];
int cnt = 0;
int f[N];
int ans[N];
const int inf = INT_MAX;
void init()
{
	for(int i = 2;i <= N;i++)
	{
		if(!vis[i])
		{
			prim[++cnt] = i;
			f[i] = 1;
		}
		for(int j = 1;j <= cnt && i*prim[j] <= N;j++)
		{
			vis[i*prim[j]] = 1;
			if(i % prim[j] == 0) break;
		}
	}
}
int main (){
	init();
	int t;
	scanf("%d",&t);
	for(int i = 1;i <= N;i++)
	{
		if(f[i]) continue;
		for(int j = 1;j <= cnt && prim[j] <= i;j++)
		{
			if(!f[i-prim[j]])
			{
				f[i] = 1;
				break;
			}
		}
	}
//	cout << "true" << endl;
	for(int i = 2;i <= N;i++)
	{
		if(f[i])
		{
			ans[i] = inf;
//			cout << cnt << endl;
			for(int j = 1;j <= cnt && prim[j] <= i;j++)
			{
//				cout << j << endl;/
				if(f[i-prim[j]])
				{
					ans[i] = min(ans[i],inf);
				}
				else
				{
					ans[i] = min(ans[i],ans[i-prim[j]]+1);
				}
			}
		}
		else
		{
			ans[i] = 0;
			for(int j = 1;j <= cnt && prim[j] <= i;j++)
			{
				if(f[i-prim[j]])
				{
					ans[i] = max(ans[i],ans[i-prim[j]]+1);
				}
				else
				{
					ans[i] = max(ans[i],ans[i-prim[j]]+1);
				}
			}
		}
	}
//	cout << "true" << endl; 
	while(t--)
	{
		int n;
		scanf("%d",&n);
		if(!f[n]) cout << -1 << endl;
		else cout << ans[n] << endl; 
	}
	return 0;
}