#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define maxn 100009
using namespace std;
int flag[maxn],p[maxn],tot;
long long n;
void init(){
    for(int i=2;i<maxn;i++){
        if(!flag[i])
            p[tot++]=i;
        for(int j=0;j<tot&&i*p[j]<maxn;j++){
            flag[i*p[j]]=1;
            if(i%p[j]==0)
                break;
        }
    }
}
bool prime(long long x){
    for(int i=0;i<tot&&1LL*p[i]*p[i]<=x;i++)
        if(x%p[i]==0)
            return 0;
    return 1;
}
bool check(long long x){
    for(int i=0;i<tot&&1LL*p[i]*p[i]<=x;i++)
        if(x%(1LL*p[i]*p[i])==0)
            return 0;
    return 1;
}
long long solvel(){
    long long ans=-1;
    long long L=1,R=1e9+7;
    while(L<R){
        long long M=(L+R+1)>>1;
        if(M*M<=n)
            L=M;
        else
            R=M-1;
    }
    long long tmp=L;
    while(tmp>=2){
        if(prime(tmp))
            break;
        tmp--;
    }
    for(long long i=tmp;i<=L;i++){
        if(i*i<2) continue;
        if(check(i))
            ans=i;
    }
    if(ans==-1) return ans;
    else return ans*ans;
}
long long solver(){
    long long ans=-1;
    long long L=1,R=1e9+7;
    while(L<R){
        long long M=(L+R)>>1;
        if(M*M>n)
            R=M;
        else
            L=M+1;
    }
    long long tmp=R;
    while(1){
        if(prime(tmp))
            break;
        tmp++;
    }
    for(long long i=R;i<=tmp;i++){
        if(i*i<2) continue;
        if(check(i)){
            ans=i;
            break;
        }
    }
    if(ans==-1) return ans;
    else return ans*ans;
}
int main(){
    init();
    int tt;
    scanf("%d",&tt);
    while(tt--){
        scanf("%I64d",&n);
        long long ans1=solvel();
        long long ans2=solver();
        if(ans1==-1){
            printf("%I64d\n",ans2-n);
            continue;
        }
        if(ans2==-1){
            printf("%I64d\n",n-ans1);
            continue;
        }
        printf("%I64d\n",min(n-ans1,ans2-n));
    }
    return 0;
}