Problem 1041 --一起来找数

1041: 一起来找数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 49  Solved: 9
[Submit][Status][Web Board][Creator:]

Description

有一天,mirror给了kyoma一个数x,让kyoma找到一个正整数y>=2,使得y-x的绝对值最小。
但是kyoma觉得这样做太简单了,于是她反问mirror,要求在满足上一个条件的同时,这个y中的每个质因数均恰好出现2次。
mirror感到很困难,你能够帮帮她吗?

Input

第一行输入一个整数T(1<=T<=50)
每组数据有一行,一个整数x(1<=x<=10^18)

Output

对于每组数据,输出一行y-x的最小绝对值

Sample Input

5
1112
4290
8716
9957
9095

Sample Output

23
65
67
244
70

HINT

Source

[Submit][Status]