P4318 Perfect Squares

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?

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 $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$.

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