问题1041--一起来找数

1041: 一起来找数

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

提交

题目描述

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

输入

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

输出

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

样例输入 Copy

5
1112
4290
8716
9957
9095

样例输出 Copy

23
65
67
244
70