#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cmath>
using namespace std;
typedef long long LL;
typedef double db;
typedef pair<int,int>p1;
const int maxn=40005;
int vis[maxn];
int prim[maxn];
int tot;
void init(){
    for(int i=2;i<maxn;i++){
        if(!vis[i]) prim[tot++]=i;
        for(int j=2*i;j<maxn;j+=i){
            vis[j]=1;
        }
    }
}
int panduan(int p){
    for(int i=0;prim[i]*prim[i]<=p;i++){
        if(p%(prim[i]*prim[i])==0){
            return 0;
        }
    }
    return 1;
}
LL get(LL a){
    if(a<0) a=-a;
    return a;
}
int main()
{
    int t;
    LL x;
    cin>>t;
    init();
    while(t--){
        scanf("%I64d",&x);
        LL re=(LL)1<<60;
        int q=sqrt(x);
        for(int i=max(2,q-300);i<=q+300;i++){
            if(panduan(i)){
                LL q=get(x-(LL)i*i);
                if(q<re){
                    re=q;
                }
            }
        }
        printf("%I64d\n",re);
    }
}