#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 45005
#define Tl tree[l]
#define Tr tree[r]
#define Tp tree[p]
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define rep(i,s,t) for(int i=s;i<=t;++i)
#define rrep(i,s,t) for(int i=s;i>=t;--i)
bool mark[45005];
int prime[50000],cnt=0;
int mp[1000000],id;
using namespace std;
typedef long long ll;
inline void Rd(int &res){
    char c;res=0;
    while(c=getchar(),c<48);
    do res=res*10+(c&15);
    while(c=getchar(),c>47);
}
void list(){
    int i,j;
    for(i=2;i<M;i++)
        if(!mark[i]){
            prime[++cnt]=i;
            for(j=i;j<M;j+=i)
                mark[j]=1;
        }
}
long long n;
int A[M];
bool check(int a){
    for(int i=1;i<=cnt;i++){
        int c=0;
        while(a%prime[i]==0){
            c++;
            a/=prime[i];
        }
        if(c>1)return false;
        if(a==1)break;
    }
    return true;
}
void solve(ll x){
    int res=(int)(sqrt(x));
    int v=res+1,p=res;
    if(res<2)v=p=2;
    while(!check(v)){
        v++;
    }
    while(check(p)==0&&p>2){
        p--;
    }
    ll a,b;
    if(check(p))a=abs(x-1ll*p*p);
    else a=1e18;
    if(check(v))b=abs(x-1ll*v*v);
    else b=1e18;
    printf("%lld\n",min(a,b));
}
int main(){
    int T;
    list();
    scanf("%d",&T);
    ll n;
    while(T--&&scanf("%lld",&n)){
        solve(n);
    }
    return 0;
    }