#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5;
bool np[N + 1];
long long p[10000];
int cnt;
void init_prime()
{
    int m = ceil(sqrt(N));
    for (int i = 2; i <= m; i++)
        if (!np[i]) for (int j = i + i; j <= N; j += i)
            np[j] = true;
    for (int i = 2; i <= N; i++)
        if (!np[i]) p[cnt++] = i;
}
bool check(long long x)
{
    for (int i = 0; p[i] * p[i] <= x; i++)
        if (x % (p[i] * p[i]) == 0) return false;
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    init_prime();
    int t;
    cin >> t;
    while (t--)
    {
        long long x;
        cin >> x;
        long long m = max((int)sqrt(x), 2), y1, y2;
        for (y1 = m + 1; !check(y1); y1++);
        for (y2 = m; !check(y2) && y2 >= 2; y2--);
        if (y2 == 1) cout << abs(y1*y1 - x) << endl;
        else cout << min(abs(y1*y1 - x), abs(y2*y2 - x)) << endl;
    }
}