Project Euler #69: Totient maximum

_{This problem is a programming version of Problem 69 from projecteuler.net}

Euler's Totient function, [sometimes called the phi function], is used to determine the number of numbers less than which are relatively prime to . For example, as and , are all less than nine and relatively prime to nine, .

It can be seen that produces a maximum for . Find the value of for which is maximum. In case of multiple answers, print the minimum.

Input Format

First line contains , denoting number of test cases. lines follow
Each line contains

Constraints

Output Format

Print the answer corresponding to each testcase on a new line.

Sample Input

2
3
10

Sample Output

2
6