#1614 SieveOfEratosthenes

19  1 s   128 MB  

Description

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 to maxNum
   if x is not scratched
      for y = 2 to maxNum/x
         if 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.

Input

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.

Output

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