19 1 s 128 MB

The Sieve of Erathosthenes is an ancient method used to find all prime numbers between 2 and a given upper bound **maxNum**, inclusive. It works like this:

make a list of all numbers between 2 and **maxNum**, inclusive

for x = 2 tomaxNumif x is not scratched for y = 2 tomaxNum/xif x*y is not scratched, scratch x*y end for end if end for

In this fashion, every composite number in the range will get scratched while every prime number will remain unscratched. Print the last number which gets scratched when the Sieve of Eratosthenes is run with the given **maxNum**.

The first line of the input gives the number of test cases, $T$ $(1 \leq T \leq 200)$.

For each test case one positive integer **maxNum **will be given in a line. **MaxNum **will be between $4$ and $2\times10^9$, inclusive.

For each test case, print the last number as explained in the problem statement, in one line.

## Sample Input | ## Sample Output |
---|---|

4 18 5 100 400 | 15 4 91 361 |