#include<bits/stdc++.h>
using namespace std;
bool pr[1000000];
long long vis1[1000000],f1[1000000],vis2[1000000],f2[1000000],pri[1000000],ll;
long long dp2(int);
long long dp1(int n){
	//printf("%d\n",n);
	if(vis1[n])return f1[n];
	vis1[n]=1;
	for(int i=0;pri[i]<=n;i++)
	f1[n]=min(f1[n],1+dp2(n-pri[i]));
	return f1[n];
}
long long  dp2(int n){
//	printf("%d\n",n);
	if(vis2[n])return f2[n];
	vis2[n]=1;
	for(int i=0;pri[i]<=n;i++)
	f2[n]=max(f2[n],1+dp1(n-pri[i]));
	return f2[n];
}
int main()
{
	vis1[0]=vis1[1]=1;
	vis2[0]=vis2[1]=1;f2[0]=0;f2[1]=0;
	for(int i=0;i<=20000;i++)f1[i]=1000000000;
	for(long long i=2;i<=20000;i++){
		if(pr[i]==0){
			vis1[i]=1;f1[i]=1;vis2[i]=1;f2[i]=1000000000;
			pri[ll++]=i;
			for(long long j=i*i;j<=20000;j+=i)pr[j]=1;
		}
	}
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		int n;scanf("%d",&n);
		printf("%lld\n",dp1(n)>=1000000000?-1:dp1(n));
	}
	return 0; 
}