IAPCR2D - Find The Number

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.

Constraints

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

Added by:imranziad
Date:2016-06-03
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Intra AIUB Programming Contest (Jamil Siam)

hide comments
2017-06-26 09:34:48
precomputation + binary search works....plz consider n=0...it costed me 3 wa's
2016-10-11 07:12:28 shahzada
n=0 costed 3 WAs!!
2016-06-29 10:39:31
Ahh, mixed feelings because my python solution did not pass but pypy solution passed. Too lazy to look for optimizations on such easy problem. :/
2016-06-12 00:53:38 sankalp sharma
How to do it in 0.00 ? It took me 0.02 sec with precomputation+log n

Last edit: 2016-06-15 20:12:02
2016-06-11 07:43:29 fitcat
n can be greater than 10^18.
2016-06-07 20:45:06 Piyush Kumar
If X is guranteed to be less than 10^2+10, why do we have to print nai for X>10^4!
2016-06-06 18:12:24
how do you precompute factorials of 110 and all? could someone help here?
2016-06-03 19:28:59
precomputation works....<3..
2016-06-03 16:30:54 anonymous
Francky: I got AC with assumption that it is simply 110.
2016-06-03 15:46:31 Francky
Is there a typo, or 10^2 + 10 is simply 110 ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.