#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

#define rep(i, l, r) for(int i=l; i<=r; i++)
#define dow(i, l, r) for(int i=l; i>=r; i--)
#define clr(x, c) memset(x, c, sizeof(x))
#define travel(x) for(edge *p=fir[x]; p; p=p->n)
#define all(x) (x).begin,(x).end
#define pb push_back
#define fi first
#define se second
#define l(x) Left[x]
#define r(x) Right[x]
#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef long double ld;
typedef unsigned long long ull;

inline int read()
{
    int x=0; bool f=0; char ch=getchar();
    while (ch<'0' || '9'<ch) f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9') x=x*10+ch-'0', ch=getchar();
    return f?-x:x;
}

inline ll cal(ll x)
{
    ll l=1, r=sqrt(x), mid; while (r*r<x) r++; while (l<r)
    {
        mid=(l+r)>>1;
        if ((mid+1)*(mid+1)<=x) l=mid+1; else r=mid;
    }
    return l;
}

#define maxn 100009

int pri[maxn], pn; bool b[maxn];

inline bool jub(ll x)
{
    rep(i, 1, pn) if (x%(pri[i]*pri[i])==0) return false; else if (pri[i]*pri[i]>x) return true;
    return true;
}

int main()
{
    rep(i, 2, 1e5)
    {
        if (!b[i]) pri[++pn]=i;
        rep(j, 1, pn) if (i*pri[j]<=1e5)
        {
            b[i*pri[j]]=1;
            if (i%pri[j]==0) break;
        } else break;
    }
    int t=read(); while (t--)
    {
        ll x; scanf("%lld", &x); ll y=cal(x);
        if (x<=4) printf("%lld\n", abs(x-4)); else
        {
            ll l=y, r=y+1, A;
            while (true)
            {
                if (l!=1 && abs(l*l-x)<=abs(r*r-x))
                {
                    if (jub(l)) {A=l; break;} else l--;
                }
                else
                {
                    if (jub(r)) {A=r; break;} else r++;
                }
            }
            printf("%lld\n", abs(A*A-x));
        }
    }
    return 0;
}