#include<bits/stdc++.h>
using namespace std;
#define N 20002000
typedef long long ll;
int T;
bool ntp[N];
int p[N>>2],pn;
void init(int n){
	ntp[1]=ntp[0]=1;
	for(int i=2;i<=n;++i){
		if(!ntp[i])p[++pn]=i;
		for(int j=1;j<=pn&&p[j]*i<=n;++j){
			ntp[p[j]*i]=1;
			if(i%p[j]==0)break;
		}
	}
}
int x;
int calc(int x){
	while(true){
		if(!ntp[x+1]){
			return 2*x+2;
		}
		else if(!ntp[x+x+3]){
			return 2*x+3;
		}
		++x;
	}
}
void Solve(){
	cin>>x;
	if(x<=0){
		cout<<calc(-x)<<'\n';
	}
	else{
		if(!ntp[x]){
			cout<<1<<'\n';
		}
		else if(!ntp[2*x-1]||!ntp[2*x+1]){
			cout<<2<<'\n';
		}
		else{
			cout<<calc(x)<<'\n';
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	init(20000233);
	cin>>T;
	while(T--){
		Solve();
	}
	return 0;
}