Having gained some experience with Prime Numbers, Robin now seeks Revenge from Bruce. So, while they are on their way from the Airport to the Summit, Robin comes up with a new Prime based Puzzle for Bruce.

He asks him to find rad(n) for t numbers which he lists before Bruce and then form a sorted table on the values of rad(n) (in ascending order) and he defines rad(n) as the product of the distinct prime factors of n. He then asks him to find E(k) which he defines as the kth element in the sorted table. Bruce has got to prepare for the Summit and so he seeks your help. Help him solve this puzzle to maintain his status as the The Dark Knight of Gotham.

Input:
First line contains t, the number of testcases, and t lines follow after it each containing a single integer k.

Output: Display E(k) for each value of n in a separate line

Constraints:

t ≤ 500

k ≤ 10000

Table is made for n values till 10000SAMPLE INPUT
5
1
3
5
6
10

SAMPLE OUTPUT
1
4
3
9
10

Explanation

Refer the table for n values till 10 in the question description and Cross-Reference it with the sample input/output.

见题面

见题面