Description

Xiao X has liked numbers since childhood. Strangely, he hates perfect squares other than $1$. He finds those numbers unpleasant to look at. As a result, he also hates every positive integer that is a multiple of these perfect squares. However, this does not affect his love for all the other numbers.

It is Xiao X’s birthday, and Xiao W wants to give him a number as a gift. Of course, he cannot give a number that Xiao X hates. He listed all the numbers that Xiao X does not hate and then chose the $K$-th number to give to Xiao X. Xiao X happily accepted it.

Now Xiao W cannot remember which number he gave to Xiao X. Can you help him?

Input Format

Multiple test cases. The first line contains an integer $T$, the number of test cases.
From the $2$-nd to the $(T+1)$-th lines, each line contains an integer $K_i$, describing one test case as stated above.

Output Format

Output $T$ lines, one answer per test case. In the $i$-th line, output the $K_i$-th positive integer that is not a multiple of any perfect square greater than $1$.

4 
1 
13 
100 
1234567

1 
19 
163 
2030745

Hint

For 50% of the testdata, $1 \le K_i \le 10^5$.
For 100% of the testdata, $1 \le K_i \le 10^9$, $T \le 50$.

Translated by ChatGPT 5