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
hide comments
viratian_070:
20170626 09:34:48
precomputation + binary search works....plz consider n=0...it costed me 3 wa's 

shahzada:
20161011 07:12:28
n=0 costed 3 WAs!! 

dwij28:
20160629 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. :/ 

sankalp sharma:
20160612 00:53:38
How to do it in 0.00 ? It took me 0.02 sec with precomputation+log n Last edit: 20160615 20:12:02 

fitcat:
20160611 07:43:29
n can be greater than 10^18. 

Piyush Kumar:
20160607 20:45:06
If X is guranteed to be less than 10^2+10, why do we have to print nai for X>10^4! 

akshayvenkat:
20160606 18:12:24
how do you precompute factorials of 110 and all? could someone help here? 

azam_9:
20160603 19:28:59
precomputation works....<3.. 

anonymous:
20160603 16:30:54
Francky: I got AC with assumption that it is simply 110. 

Francky:
20160603 15:46:31
Is there a typo, or 10^2 + 10 is simply 110 ? 
Added by:  imranziad 
Date:  20160603 
Time limit:  0.300s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Intra AIUB Programming Contest (Jamil Siam) 