#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#define m_p make_pair
#define p_b push_bakc
#define fi first
#define se second
#define LL long long
using namespace std;
const int maxn = 100010;
bool flag[maxn];
int prime[maxn];
int px[100];
int a[maxn];
int tot=0;

bool ok(int x)
{
    int p=x,k=0;
    memset(px,0,sizeof(px));
    for (int i=1; i<=tot; i++)
    {
        if (p<=1e5 && flag[p]) break;
        if (p % prime[i]==0)
        {
            k++;
            while (p % prime[i]==0)
            {
                p/=prime[i];
                px[k]++;
            }
        }
    }
    bool bb=1;
    for (int i=1; i<=k; i++)
        if (px[i]!=1)
            bb=0;
    return bb;
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    memset(flag,1,sizeof(flag));

    for (int i=2; i<=maxn-10; i++)
        if (flag[i])
        {
            prime[++tot]=i;
            for (int j=i+i; j<=maxn-10; j+=i)
                flag[j]=0;
        }
    int tt; scanf("%d",&tt);
    while (tt--)
    {
        LL n;
        scanf("%I64d",&n);
        int tmp=sqrt((long double) n);
        while ((LL) tmp*tmp>n) tmp--;
        int tmp1=max(2,tmp)+1;
        int tmp2=tmp1-1;
        while (!ok(tmp1)) tmp1++;
        while (tmp2>2 && !ok(tmp2)  ) tmp2--;
        LL ans=min(abs((LL) tmp1*tmp1-n),abs((LL) tmp2*tmp2-n));
        //printf("%d\n%d\n",tmp1,tmp2);
        printf("%I64d\n",ans);
    }

    return 0;
}