#include<bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define eb emplace_back
#define fi first
#define se second
#define pc __builtin_popcount
typedef pair<int,int> pii;
typedef vector<int> vi;

long long read() {
	long long res=0, w=1; char c=getchar();
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) {res=res*10+c-'0'; c=getchar();}
	return res*w;
}

const int N=2e7+9;
int pr[N],tot,vst[N],nxt[N];
int T,x[N];

void pre(int n=2e7) {
	vst[1]=1;
	rep(i,2,n) {
		if(!vst[i]) pr[++tot]=i;
		for(int j=1;j<=tot&&pr[j]*i<=n;j++) {
			vst[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}
	per(i,n,0) {
		if(!vst[i]) nxt[i]=i;
		else nxt[i]=nxt[i+1];
	}
}

signed main() {
	T=read();
	pre();
	rep(i,1,T) {
		int x=read();
		if(x==0) {
			puts("3");
		} else if(x>0&&!vst[x]) {
			puts("1");
		} else if(x>0&&(!vst[2*x+1]||!vst[2*x-1])) {
			puts("2");
		} else {
			int l=x, r=2-x, ans=1e9;
			if(l>r) swap(l,r);
			if(!vst[r-l+1]) ans=min(ans,r-l+1);
			l=x, r=1-x;
			if(l>r) swap(l,r);
			int len=r-l+1;
			if(len%2==0) len/=2;
			if(!vst[len]) ans=min(ans,r-l+1);
			if(ans==1e9) ans=-1;
			printf("%lld\n",ans);
		}
	}
	return 0;
}