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.
First line contains , denoting number of test cases. lines follow
Each line contains
Print the answer corresponding to each testcase on a new line.