#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for (int i = (l); i <= (r); i++)
#define per(i,r,l) for (int i = (r); i >= (l); i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define maxn(a, b) a = max(a, b)
#define minn(a, b) a = min(a, b)
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const ll mod = 998244353;
mt19937 gen(random_device{}());
ll rp(ll a,ll b) {ll res=1%mod;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int N = 3e7;
const int inf = 1e9;
bool b[N];
VI ve;

void solve() {
    int n;
    scanf("%d", &n);
    // (l + r) * 1ll * (r - l + 1) / 2;
    if (n == 0) {
        puts("3");
        return ;
    }
    if (n>0&&!b[n]) return void(puts("1"));
    if (n>0&&(!b[2 * n - 1] || !b[2 * n + 1])) {
        return void(puts("2"));
    }
    int ans = inf;
    int m = abs(n) + 1;
    while (b[m+m+1]) m++;
    minn(ans, 2 * m+1);

    m=abs(n)+1;
    while (b[m]) m++;
    minn(ans, 2 * m);

    printf("%d\n", ans);
    return ;
}

void init() {
    b[0] = b[1] = 1;
    rep(i,2,N-1){
        if(!b[i]) ve.pb(i);
        for(auto j:ve){
            if(i*1ll*j>=N)break;
            b[i*j]=true;
            if(i%j==0) break;
        }
    }
}

int main() {
    init();
    int T;
    scanf("%d", &T);
    while (T--)
        solve();
    return 0;
}