#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=4e7+9;
int pr[N],tot,vst[N],nxt[3][N];
int T,x[N];

void pre(int n=4e7) {
	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/2,0) {
		if(!vst[i]) nxt[1][i]=i;
		else nxt[1][i]=nxt[1][i+1];
		if(!vst[2*i-1]) nxt[2][i]=i;
		else nxt[2][i]=nxt[2][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 {
			if(x<0) x=-x;
			printf("%lld\n",2*x+1+min(2*(nxt[1][x+1]-x-1)+1,2*(nxt[2][x+2]-x-2)+2));
		}
	}
	return 0;
}