//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
bool isp[30003000];
int nxt[30003000],nxt2[30003000];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(isp,1,sizeof(isp));
	isp[0]=isp[1]=0;
	for(int i=2;i<30003000;i++)
		for(int j=i+i;j<30003000;j+=i)
			isp[j]=0;
	for(int i=30000000;i>=0;i--)
		if(isp[i])
			nxt[i]=i;
		else
			nxt[i]=nxt[i+1];
	for(int i=1.2e7;i>=0;i--)
		if(isp[i+i+1])
			nxt2[i]=i;
		else
			nxt2[i]=nxt2[i+1];
	int t;
	cin>>t;
	while(t--)
	{
		int x;
		cin>>x;
		if(x<=0)
		{
			x*=-1;
			if(isp[x+1])
				cout<<x+x+2<<'\n';
			else if(isp[x+1+x+2])
				cout<<x+x+3<<'\n';
			else
			{
				int y=nxt[x+1];
				int ans=y+y;
				int z=nxt2[x+1];
				ans=min(ans,z+z+1);
				cout<<ans<<'\n';
			}
		}
		else
		{
			if(isp[x])
				cout<<1<<'\n';
			else if(isp[x+x-1]||isp[x+x+1])
				cout<<2<<'\n';
			else
			{
				int y=nxt[x];
				int ans=y+y;
				int z=nxt2[x];
				ans=min(ans,z+z+1);
				cout<<ans<<'\n';
			}
		}
	}
	return 0;
}