#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("%lld",&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("%lld\n",sum);
    }
    return 0;
}