背景 Background

__int64 ago,there's a heaven cow called sjy...
A god bull named wzc fell in love with her...
As an OI & MOer,wzc gave sjy a quesiton...

描述 Description

给定一个整数n，求一个整数m，满足m<=n，并且m/phi(m)的值最大。
注：phi(m)代表m的欧拉函数，即不大于m且与m互质的数的个数。

输入格式 Input Format

第一行是一个整数T，表示该测试点有T组数据。
接下来T行，每行一个整数n，意义如上所述。

输出格式 Output Format

输出一共T行，每行一个整数m。
若对于某个n，有不止一个满足条件的m，则输出最小的m。

样例输入 Sample Input

1
10

样例输出 Sample Output

6

时间限制 Time Limitation

各个测试点1s

注释 Hint

对于10%的数据, n<=1000
对于30%的数据, n<=10^10
对于60%的数据, n<=10^2000
对于100%的数据，T<=100，n<=10^25000。