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