#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = 0x7fffffffffffffffll;
LL n;
LL ans;
bool judge(LL x){
    if(x < 2) return false;
    LL t = x;
    for(LL i = 2; i * i <= x; i ++){
        if(x % i == 0){
            if(x % (i*i) == 0) return false;
            x /= i;
        }
    }
    ans = min(ans, abs(t*t - n));
    return true;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        scanf("%I64d", &n);
        LL x = (LL)(sqrt(n) + 0.5);
        int f = 0;
        ans = INF;
        for(int i = 0;; i ++){
            if(judge(x+i)) f = 1;
            if(judge(x-i)) f = 1;
            if(f == 1) break;
        }
        printf("%I64d\n", ans);
    }
}