#include<bits/stdc++.h>
using namespace std;const unsigned N=2e4+1;
#define void inline void
#define int register unsigned
bitset<N>v;unsigned p[N]={2},cnt,dp[N];
void mn(int &a,int b){a>b?a=b:0;}void mx(int &a,int b){a<b?a=b:0;}
void init(){for(int i=3,j;i<N;i+=2){if(!v[i])p[++cnt]=i;for(j=1;p[j]*i<N;++j)v[i*p[j]]=1;}}
void get_v(){v.reset();for(int i=2,j;i<N;++i)for(j=0;j<=cnt&&p[j]<=i;++j)v[i]=v[i]|(v[i-p[j]]^1);}
void DP(){for(int i=1,j;i<N;++i){dp[i]=v[i]?~0:0;for(j=0;j<=cnt&&p[j]<=i;++j)v[i]?mn(dp[i],v[i-p[j]]?~0:dp[i-p[j]]+1):mx(dp[i],dp[i-p[j]]+1);}}
signed main(){ios::sync_with_stdio(0);init();get_v();DP();int n,x;cin>>n;
	while(n--){cin>>x;if(v[x])cout<<dp[x]<<'\n';else cout<<"-1\n";}}