题目描述

给定一个整数$\red{n，}$求一个整数$\red{m，}$满足$\red{m<=n，}$并且$\red{m/phi(m)}$的值最大。

注：$\red{phi(m)}$代表$\red{m}$的欧拉函数，即不大于$\red{m}$且与$\red{m}$互质的数的个数。

输入格式

第一行是一个整数$\red{T，}$表示该测试点有$\red{T}$组数据。

接下来$\red{T}$行，每行一个整数$\red{n，}$意义如上所述。

输出格式

输出一共$\red{T}$行，每行一个整数$\red{m}$。

若对于某个$\red{n，}$有不止一个满足条件的$\red{m，}$则输出最小的$\red{m}$。

样例

输入样例

1
10

输出样例

6

提示

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