#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=30005000;
bool notp[maxn+50];
int pcnt=0;
int prim[(maxn>>3)+50];
void prepare(){
	notp[1]=1;
	for (ll i=2;i<=maxn;i++){
		if (!notp[i]){
			prim[++pcnt]=i;
		}
		for (ll j=1,x;j<=pcnt && (x=i*prim[j])<=maxn;j++){
			notp[x]=1;
			if (i%prim[j]==0){
				break;
			}
		}
	}
}
inline bool isprime(ll x){return !notp[x];}

ll solve(ll n){
	if (n==0) return 3;
	if (n>0){
		if (isprime(n)) return 1;
		if (isprime(2*n-1)) return 2;
		if (isprime(2*n+1)) return 2;
		for (ll x=n-1;x<=maxn;x++){
			if (isprime(x+1)){
				return (x)+1+(x+1);
			}
			if (isprime(x+1+x+2)){
				return (x)+1+(x+2);
			}
		}
	}
	else{
		ll t=abs(n);
		if (isprime(t+1)) return (t)+1+(t+1);
		if (isprime(t+1+t+2)) return (t)+1+(t+2);
		
		for (ll x=t;x<=maxn;x++){
			if (isprime(x+1)){
				return (x)+1+(x+1);
			}
			if (isprime(x+1+x+2)){
				return (x)+1+(x+2);
			}
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	prepare();
	int TC=1;
	cin >> TC;
	for (;TC--;){
		ll n;
		cin >> n;
		cout << solve(n) << "\n";
	}
	return 0;
}