Limits 1s, 512 MB

NOD(X)NOD(X) is the number of divisors of X. For example, NOD(10)NOD(10) is 4. 10 has 4 divisors: 1, 2, 5, and 10.

Similarly, NOD(15)NOD(15) is also 4.

In this problem, you will be given an integer NN. You will have to determine the NN-th positive integer for which NODNOD is odd.

Input

The first line of the input contains a single integer TT (1T1000001 \le T \le 100000) denoting the number of test cases.

Each test case contains a number NN (1N1000000001 \le N \le 100000000).

Output

For each test case print the NN-th positive integer having an odd number of divisors.

Sample

InputOutput
1
1
1

Submit

Login to submit.

Statistics

90% Solution Ratio
mhridoyEarliest, Jan '18
Imran02Fastest, 0.0s
mjannatLightest, 1.6 MB
bokaifShortest, 36B
Toph uses cookies. By continuing you agree to our Cookie Policy.