#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>

#define F first
#define S second
#define mp make_pair
using namespace std;
typedef __int64 LL;
const int maxn = 1e5+10;
LL prime[maxn];
LL cit[maxn],len;
void init()
{
    prime[0]=prime[1]=true;
    for(int i=2;i<=101000;i++)
    {
        if(!prime[i])
        {
            if(i>101000/i) continue;
            for(int j=i*i;j<=101000;j+=i)
                prime[j]=true;
        }
    }
    len=0;
    for(int i=2;i<=101000;i++)
    {
        if(!prime[i])
        cit[len++]=i;
    }
}

bool ok(int x)
{
    if(x==1) return false;
    for(int i=0;i<len;i++)
    {
        if(x%cit[i]==0)
        {
            x/=cit[i];
            if(x%cit[i]==0) return false;
        }
    }
    return true;
}
int main()
{
    init();
    int T ;
    scanf("%d",&T);
    while(T--)
    {
        LL x;
        scanf("%I64d",&x);
        LL y=sqrt(x);
        LL a,b;
        bool flag1=false;
        bool flag2=false;
        LL ans=1e18+10;
        if(ok(y))
            ans=min(ans,abs(y*y-x));
             a=b=-1;
        for(int i=1;;i++)
        {
            if(!flag1&&ok(y+i))
            {
                a=y+i;
                flag1=true;
            }
            if(!flag2&&ok(y-i)&&y-i>0)
            {
                b=y-i;
                flag2=true;
            }
            if(y-i<=0) flag2=true;
            if(flag1&&flag2) break;
        }
        if(a!=-1) ans=min(ans,abs(a*a-x));
        if(b!=-1) ans=min(ans,abs(b*b-x));
        printf("%I64d\n",ans);
    }
    return 0;
}