#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 3e7 + 7, INF=0x3f3f3f3f, MOD = 998244353;

bool np[N];
int minn[N];
void init(){
	np[0]=np[1]=true;
	for(int i=2;i<N;i++){
		if(np[i]) continue;
		minn[i]=i;
		for(int j=2*i;j<N;j+=i) np[j]=true;
	}
	minn[N-1]=INF;
	for(int i=N-2;i>=0;i--){
		if(!minn[i]) minn[i]=minn[i+1];
	}
}

int x,ans;

void solve() {
	cin>>x;
	ans=INF;
	if(x>=0&&!np[x]) ans=min(ans,1);
	if(2*x-1>=0&&!np[2*x-1]||2*x+1>=0&&!np[2*x+1]) ans=min(ans,2);
	int maxn=max(3,max(3-2*x,2*x-1));
	ans=min(ans,minn[maxn]);
	maxn=max(3,max(x,1-x));
	ans=min(ans,2*minn[maxn]);
	if(x>=-1&&x<=2) ans=min(ans,4);
	cout<<ans<<'\n';
}

int main() {
	init();
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tc = 1;
	cin >> tc;
	while (tc--) solve();
	return 0;
}