Very Simple

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

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

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

Input

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

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

Output

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

Sample

1
1

1