http://acm.hdu.edu.cn/showproblem.php?pid=5778
思路：只有平方质因子的数，也就是这题所说的 y的质因数分解式中每个质因数均恰好出现2次 满足条件的数很幂集
因此枚举sqrt(x)，前后判断一下sqrt(x)的质因子就可以
可以不判断是不是素数
注意x<4的情况
// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define pi acos(-1.0)
const int N = + ;
#define inf 0x7fffffff
typedef long long LL; void fre() { freopen("in.txt","r",stdin);} bool isPrime[N];
LL primeList[N],primeCount = ; LL Fast_power(LL n,LL k,LL mod) {
if(k == ) return ;
LL temp = Fast_power(n,k / ,mod);
temp = (temp * temp) % mod;
if(k % == ) temp = (temp * (n % mod)) % mod;
return temp;
} void Eular_Sieve(LL n) {
memset(isPrime,true,sizeof(isPrime));
isPrime[] = false;
isPrime[] = false;
for(int i = ; i <= n; i ++) {
if(isPrime[i]) {
primeCount ++;
primeList[primeCount] = i;
}
for(int j = ; j <= primeCount; j ++) {
if(i * primeList[j] > n) break;
isPrime[i * primeList[j]] = false;
if(!(i % primeList[j])) break;
}
}
} int Mr[] = {, , , , , , , , , , , };
bool Miller_Rabin(LL n) {
if(n == ) return true;
else if(n < ) return false;
if(n % == ) return false;
LL u = n - ;
while(u % == ) u = u / ;
int tempu = u;
for(int i = ; i < ; i ++) {
if(Mr[i] >= n) break;
u = tempu;
LL x = Fast_power(Mr[i],u,n);
while(u < n) {
LL y = (x % n) * (x % n) % n;
if(y == && x != && x != n - ) return false;
x = y;
u = u * ;
}
if(x != ) return false;
}
return true;
} int main() {
// fre();
Eular_Sieve();
int T;
scanf("%d",&T);
while(T --) {
LL n;
scanf("%I64d",&n);
if(n<=){
printf("%d\n",-n);
continue;
}
LL x = sqrt(n);
LL y = sqrt(n) + ;
LL cnt = ,ans = ;
while() {
LL xx = x - cnt;
if(Miller_Rabin(xx)) {
ans = n - xx * xx;
break;
} else {
LL pp = xx;
bool flag = true;
for(int i = ; i < primeCount && i * i <= pp; i ++) {
int cou = ;
while(pp % primeList[i] == ) {
pp = pp / primeList[i];
cou ++;
if(cou>=){
break;
}
}
if(cou >= ) {
flag = false;
break;
}
}
if(flag == true) {
ans = n - xx * xx;
break;
}
}
cnt ++;
}
cnt = ;
while() {
LL yy = y + cnt;
if(yy * yy - n >= ans) break;
if(Miller_Rabin(yy)) {
ans = min(ans,yy * yy - n);
break;
} else {
LL pp = yy;
bool flag = true;
for(int i = ; i < primeCount && i * i <= pp; i ++) {
int cou = ;
while(pp % primeList[i] == ) {
pp = pp / primeList[i];
cou ++;
if(cou>=){
break;
}
}
if(cou >= ) {
flag = false;
break;
}
}
if(flag == true) {
ans = min(ans,yy * yy - n);
break;
}
}
cnt ++;
}
printf("%I64d\n",ans);
}
return ;
}