Professor Numerico is a number fanatic who loves to explore the properties of numbers. His apprentice, Dumdum, is your good friend, who you often help solve problems for Numerico.
The Professor is fed up with Summation and resolves to explore Multiplication. He tasks Dumdum with finding the product of a number 's divisors, or where
For example, if , then .
Dumdum proudly manages to calculate this himself. Determining the task is too easy, Professor Numerico decides to change the task by giving Dumdum a number, , and asking him to find the smallest positive integer, , whose product of divisor is (i.e.: find such that ). Dumdum isn't sure how to solve this new problem. Can you help?
Input Format
The first line contains a single positive integer, , denoting the number of test cases.
The subsequent lines each contain a single positive integer, .
Constraints
For 33.33% Points: If exists, .
For Full Points: No additional constraints on result.
Output Format
For each test case, print the smallest positive integer such that the product of 's divisors is equal to . If there is no such , print .
Sample Input
3
1
8
36
Sample Output
1
4
6
Explanation
For , as 's only divisor is , which equals .
For , as the product of 's divisors is , which equals .
For , as the product of 's divisors is , which equals .