n-th Square Free#6352
A positive integer is said to be squarefree if it is not divisible by any perfect square larger than . For example, the first few squarefree numbers are \{1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, \ldots\}. Find the -th smallest squarefree number.
The first line contains the number of tests . Each of the next lines contains one integer (1 \le n \le 10^9).
For each test case print in a separate line the -th smallest squarefree number.
Example 1