#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long ttt,x,end,l,r,ans;
bool su[100000],vis[1000000],an[1000000];
bool test(int x){
    for (int i=2;i<=sqrt(x);i++){
//        if (x<1000000) return an[x];
        if (x%i==0) x/=i;
        if (x%i==0) return 0;
    }
//    for (int i=0;i<=tot;i++,x*=st[i]) an[x]=1;
//    tot=0;
    return 1;
}
int main(){
    cin>>ttt;
    while (ttt--){
        cin>>x;
        l=trunc(sqrt(x));
        r=l+1;
        end=0;
        while (!end){
            if (x-l*l<r*r-x&&l!=1) {
                if (test(l)) ans=x-l*l,end=1;
                l--;
            }else {
                if (test(r)) ans=r*r-x,end=1;
                r++;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}