n-th Square Free

A positive integer is said to be squarefree if it is not divisible by any perfect square larger than 1. For example, the first few squarefree numbers are {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, ...}. Find the n-th smallest squarefree number.

Input

The first line contains the number of tests t. Each of the next t lines contains one integer n (1 ≤ n ≤ 10^9).

Output

For each test case print in a separate line the n-th smallest squarefree number.

Examples