HDU 5778 abs 数学

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e6 + 20;
int prime[maxn], total;
bool check[maxn];
void initprime() {
    for (int i = 2; i <= maxn - 20; ++i) {
        if (!check[i]) {
            prime[++total] = i;
        }
        for (int j = 1; j <= total; ++j) {
            if (i * prime[j] > maxn - 20) break;
            check[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}
bool isok(LL val) {
    if (val < 2) return false;
    bool flag = false;
    for (int i = 1; i <= total; ++i) {
        if (val < prime[i]) break;
        if (val % prime[i] == 0) {
            val /= prime[i];
            if (val % prime[i] == 0) return false;
            flag = true;
//            while (val % prime[i] == 0) {
//                val /= prime[i];
//                has++;
//                if (has == 3) return false;
//                flag = true;
//            }
        }
    }
//    if (val != 1) return false;
    return true;
}
void work() { // big prime * big prime  TLE   && 2^6 not ok
    LL val;
//    scanf("%I64d", &val);
    cin >> val;
    LL tpos = val;
    val = (LL)sqrt(val * 1.0);
    LL mid = 2e18;
    if (isok(val)) {
        mid = val * val;
    }
    LL big = 2e18, small = 2e18;
    for (int res = 1; ; ++res) {
        if (isok(val + res)) {
            big = (val + res) * (val + res);
            break;
        }
    }
    for (int res = 1; ; ++res) {
        if (val - res < 2) break;
        if (isok(val - res)) {
            small = (val - res) * (val -res);
            break;
        }
    }
    LL ans = min(abs(tpos - big), abs(tpos - small));
    ans = min(ans, abs(tpos - mid));
//    cout << big << " " << mid << " " << small << endl;
    cout << ans << endl;
}
int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
//    IOS;
    initprime();
//    cout << isok(33) << endl;
    int t;
    scanf("%d", &t);
    while (t--) work();
    return 0;
}