#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

const int mx=1000006;
long long p[mx],vs[mx];
int pn;

void f()
{
    vs[0]=vs[1]=1;
    pn=0;
    for (int i=2;i<mx;i++)
    {
        if (!vs[i]) p[pn++]=i;
        for (int j=0;j<pn;j++)
        {
            if (i*p[j]>=mx) break;
            vs[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

bool check(long long x)
{
    for (int i=0;p[i]<x,i<pn;i++)
    {
        if (x%p[i]==0)
        {
            x/=p[i];
            if (x%p[i]==0) return false;
        }
    }
    return true;
}

int main()
{
    int t;
    f();
    scanf("%d",&t);
    while (t--)
    {
        long long x,ans;
        scanf("%I64d",&x);
        if (x<=6)
        {
            printf("%I64d\n",abs(4-x));
            continue;
        }
        long long y=sqrt(x);
        for (long long i=y+1;;i++)
        {
            if (check(i))
            {
                ans=i*i-x;
                break;
            }
        }
        for (long long i=y;;i--)
        {
            if (check(i))
            {
                ans=min(ans,x-i*i);
                break;
            }
        }
        printf("%I64d\n",ans);
    }
}