#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long  ll;
ll x;
int T;
bool ok(ll a)
{
    for(ll i=2;i<=sqrt(a);i++){
        int ans = 0;
        while(1){
            if(ans>=2) return false;
            if(a%i==0){
                ans++;
                a/=i;
            }
            else break;
        }
    }
    return true;
}
ll c[]={0,3,2,1,0,1,2,2,1,0};
int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%I64d",&x);
        ll a=sqrt(x);
        ll sum=0;
        if(x<=9){
            sum=c[x];
        }
        else{
            ll b,c,sum1,sum2;
            for(b=a;;b--){
                if(ok(b)){
                    sum1=abs(b*b-x);break;
                }
            }
            for(c=a+1;;c++){
                if(ok(c)){
                    sum2=abs(c*c-x);break;
                }
            }
            sum=min(sum1,sum2);
        }
        printf("%I64d\n",sum);
    }
    return 0;
}