UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3034. Heaven Cow与God Bull

Statistics 下载数据

Description

__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...

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

Input

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

Output

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

Sample Input

1
10

Sample Output

6

Hint



对于100%的数据,T<=100,n<=10^25000。

Source

Poetize3