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 10000