#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN = 100000;
int prime[MAXN + 1];
void getPrime()
{
    memset(prime, 0, sizeof(prime));
    for(int i = 2; i <= MAXN; i++)
    {
        if(!prime[i])prime[++prime[0]] = i;
        for(int j = 1; j <= prime[0] && prime[j] <= MAXN / i; j++)
        {
            prime[prime[j]*i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
long long factor[100][2];
int fatCnt;
bool ok(long long x)
{
    fatCnt = 0;
    long long tmp = x;
    for(int i = 1; prime[i] <= tmp / prime[i]; i++)
    {
        factor[fatCnt][1] = 0;
        if(tmp % prime[i] == 0)
        {
            factor[fatCnt][0] = prime[i];
            while(tmp % prime[i] == 0)
            {
                factor[fatCnt][1]++;
                if(factor[fatCnt][1] != 1)
                    return false;
                tmp /= prime[i];
            }
            fatCnt++;
        }
    }
    if(tmp != 1)
    {
        factor[fatCnt][0] = tmp;
        factor[fatCnt++][1] = 1;
    }
    return true;
}
int main()
{
    getPrime();
    int t;
    cin >> t;
    while(t--)
    {
        long long n;
        cin >> n;
        long long x = sqrt(n), y = sqrt(n) + 1, c, d;
        if(x * x == n)
            y -= 2;
        for(int i = 0;; i++)
        {
            if(x + i >= 2)
            {
                if(ok(x + i))
                {
                    c = x + i;
                    break;
                }
            }
            if(x - i >= 2)
            {
                if(ok(x - i))
                {
                    c = x - i;
                    break;
                }
            }
        }
        for(int i = 0;; i++)
        {
            if(y + i >= 2)
            {
                if(ok(y + i))
                {
                    d = y + i;
                    break;
                }
            }
            if(y - i >= 2)
            {
                if(ok(y - i))
                {
                    d = y - i;
                    break;
                }
            }
        }
        c *= c;
        d *= d;
        cout << min(abs(c - n), abs(d - n)) << endl;
    }
}