For n positive integer, let F(n) = 1! × 2! × 3! × 4! × ... × n!, product of factorial(i) for i in [1..n].

Let G(n) = {i in [1..n], such that n divides F(i)}.

It is obvious that n belongs to G(n) that makes it a non empty set.

Input

The first line of input contains an integer T, the number of test cases.
On each of the next T lines, your are given an integer n.

Output

For each test case, you have to print min(G(n)).

Example

Input:
3
4
5
6

Output:
3
5
3

Explanation

For test case #1:
F(1) = 1! = 1 , not divisible by 4
F(2) = 1! × 2! = 2 , not divisible by 4
F(3) = 1! × 2! × 3! = 12 , divisible by 4
F(4) = 1! × 2! × 3! × 4! = 288 , divisible by 4
So G(4) = {3, 4}.

Constraints

0 < T < 10^4
0 < n < 10^9

A little kB of Python code can get AC in half the time limit. (Edit 2017-02-11, after the compiler changes.)
Input is not randomly chosen ;-) Have fun.