#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;

typedef long long LL;
const int N = 100010;

bool check(int x) {
    int t = x;
    for (int i = 2; i * i <= x; ++i) {
        if (t % i == 0) {
            t /= i;
            if (t % i == 0) return 0;
        }
        if (t == 1) return 1;
    }
    return 1;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        LL x;
        scanf("%I64d", &x);
        if (x == 1) {
            puts("3");
            continue;
        }
        int t = (int)sqrt(x);
        LL l, r;
        for (int i = t; ; --i) {
            if (check(i)) {
                l = i; break;
            }
        }
        for (int i = t + 1; ; ++i) {
            if (check(i)) {
                r = i; break;
            }
        }
        LL ans = min(abs(x - l * l), abs(x - r * r));
        printf("%I64d\n", ans);
    }
    return 0;
}