Migrated from Lutece 2852 养猫

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小马家养了很多猫，他给每只猫都标了从 $2$ 开始的号。但小马家的猫比较奇怪，如果两只猫的标号互质，那么这两只猫呆一起会打架，得由其他一只或几只不打架的猫过来劝架才行。

举几个例子。$2$ 号会和 $15$ 号打架。$6$ 号可以劝架，$2$ 号，$6$ 号和 $15$ 号在一起就不会出现猫猫打架。$2$ 号会和 $5$ 号打架，如果 $6$ 号和 $15$ 号一起过来劝架，$6$ 号可以让 $2$ 号与 $15$ 号不打架，之后 $15$ 号又可以劝 $2$ 号和 $5$ 号不打架（因为在此之前 $2$ 号和 $15$ 号已经被 $6$ 号劝过架了），此时 $2$ 号，$5$ 号，$6$ 号，$15$ 号就可以和谐相处了。

小马今天要带标号 $2$ 到 $N$ 的 $N-1$ 只猫外出，但是不想让他们打架，于是他需要额外带一些猫。求最小的标号 $M$，使得小马带上 $2$ 到 $M$ 的所有猫后，前 $N-1$ 只猫之间不会打架。

Input

第一行输入一个整数 $T\ (1\le T\le 10^5)$，表示数据组数。

接下来 $T$ 行，每行为一组数据，输入一个整数 $N\ (3\le N\le 10^6)$。

Output

对于每组数据，输出占一行，输出最小的满足条件的整数 $M$。如果这 $N-1$ 只猫本来就不会打架，输出 $N$ 即可。

Samples

2
3
4

6
6

Note

$2$ 号和 $3$ 号会打架，需要 $6$ 号劝架。虽然 $5$ 号会和其他猫打架，但是前 $N-1$ 只猫已经不打架了，管他的呢。

Resources

The 19th UESTC Programming Contest Preliminary