Finding the number of all divisor of a number is too easy. But don’t worry, this problem is also quite easy.

You will be given the number of all divisor of the factorial of a number, you will have to find number. If there are multiple such number, you will have to find the smallest one. If there is no such numbers that meets the constraint print “nai”.

Input

The first line of the input will be T, denoting number of test cases. In the following T lines there will be only one integer N, denoting the number of all divisor of the factorial of a number X. It is guaranteed that X will be less than 10^2 + 10.

Constrains:

1 <= t <= 10^5

0 <= n <= 10^18

1 <= X < 10^2 + 10

Output

For each test case print the number X. If X does not exists or is greater than 10^4 then print "nai" (without the quotes) in a single line. Follow the sample input/output.

Example

Input:
5
1
2
3
4
5
Output:
1
2
nai
3
nai