#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>
#include <cstdio>

using namespace std;

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (b) - 1; i >= (a); i--)

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;

const ll mod = 1000000007;
ll powmod(ll a, ll b) { ll res = 1; a %= mod; for (; b; b >>= 1) { if (b & 1) res = res*a%mod; a = a*a%mod; } return res; }

int ok(ll y) {
    if (y % 4 == 0) return 0;
    if (y % 2 == 0) y >>= 1;
    for (int i = 3; i * i <= y; i += 2) {
        if (y % i == 0) {
            y /= i;
            if (y % i == 0) return 0;
        }
    }
    return 1;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll x;
        cin >> x;
        ll y = (ll)sqrt(x);
        ll a = y, b = y + 1;
        do {
            if (a >= 4 && abs(a * a - x) < abs(b * b - x)) {
                y = a;
                a--;
            }
            else {
                y = b;
                b++;
            }
        } while (!ok(y));
        cout << abs(y * y - x) << endl;
    }
    return 0;
}