#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <stdlib.h>
#include <math.h>

#define ll __int64
#define ull unsigned long long
#define INF 1e+18
#define maxn 500500

using namespace std;

ll n, m;
bool a[maxn];
int prime[maxn / 5];
int cnt;
void creatprime()
{
    int i, j;
    a[0] = 1;
    a[1] = 1;
    for (i = 2; i*i<maxn; i++)
    {
        if (a[i] == 0)
            for (j = i*i; j<maxn; j += i)
                a[j] = 1;
    }
    cnt = 0;
    for (i = 0; i<maxn; i++)
        if (a[i] == 0)
            prime[cnt++] = i;
}



void getData() {
    scanf("%I64d", &n);
}

void solve() {
    ll x = sqrt(1.0*n);
    ll tp = x;
    ll ans = INF;
    if (n <= 4){
        printf("%I64d\n", 4 - n);
        return;
    }
    while (1) {
        if (tp < 2) break;
        ll tmp = tp;
        bool flag = 1;
        for (int i = 0; prime[i] * prime[i] <= tmp; i++) {
            if (tmp % (prime[i] * prime[i]) == 0) {
                flag = 0;
                break;
            }
            else if (tmp%prime[i] == 0) {
                tmp /= prime[i];
            }
        }
        if (flag){
            ans = min(ans, abs(n - tp*tp)); break;
        }
        tp--;
    }
    tp = x + 1;
    while (1) {
        ll tmp = tp;
        bool flag = 1;
        for (int i = 0; prime[i] * prime[i] <= tmp; i++) {
            if (tmp % (prime[i] * prime[i]) == 0) {
                flag = 0;
                break;
            }
            else if (tmp%prime[i] == 0) {
                tmp /= prime[i];
            }
        }
        if (flag) {
            ans = min(ans, abs(n - tp*tp)); break;
        }
        tp++;
        if (tp*tp - n >= ans) break;
    }
    printf("%I64d\n", ans);
}

int main() {
    creatprime();
    int t;
    scanf("%d", &t);
    while (t--) {
        getData();
        solve();
    }
    return 0;
}