MATHLOVE  Math is Love
Rashid loves mathematics. He recently started to learn how the various function works in mathematics. On his journey through the math world, he came in touch with a function named Y.
He also came to know that, here Y means the summation of number from 0 to n. For example if n = 5, then
Y = 0+1+2+3+4+5 = 15.
Now he is wondering if the knows the value of Y, can he find the value of n for the above equation?
Being so very new to the math world, he could not figure out how to approach this new problem. So he came to you for help. Can you help him?
Input:
First line of input will be T(1<=T<=100000), denoting the number of test cases.
Next T lines will contain the number Y(1<=Y<=3*10^9), value of the above function.
Output:
For each test case, if there is exist a value of n for which the above function gives the output Y then print
that value of n, otherwise if print “NAI”. (quotes for clarification).
Note: Data set is huge, use scanf,printf for faster input, output.
Sample Input
Sample Output
5
11
15
21
1
7626
NAI
5
6
1
123
hide comments
ayushgupta1997:
20170927 22:10:43
No actual binary search required, tried precomputation didn't worked failed on test case 5,simple number theory brute force works out beautifully :D 

avi_pandey:
20170719 14:28:11
easy problem . AC in one go . use inputs in double. 

Marcin:
20170528 00:03:08
There is definitely something wrong with the upper bound of the input. I got WA for 3*10^9, but correct for 10*10^9. After first few steps on doing binary search on submissions, I found that the upper bound is somewhere between 4.9*10^9 and 6.4*10^9 

Shubham Jadhav:
20170510 20:25:27
easy points :) 

candide:
20170410 12:45:55
@shreeshiv : 0 is not a valid input (because1<=Y<=3*10^9) but my own code gives answer=0. BTW, you can try Online SPOJ toolkit. Last edit: 20170411 21:25:19 

shreeshiv:
20170409 22:34:02
what is answer for 0 ,NAI or 0 

xralier:
20170407 08:42:41
anyone got AC in JAVA ? im getting TLE .. im solving this by bottom to top DP then applying binary search. I dont get it , why a problem forcing a programmer to use c/c++ ? 

candide:
20170406 18:08:18
Too easy for a classical problem. Not really brute force nor binary search, better : use basic math. Good for testing your input/output skills ;) Last edit: 20170409 14:45:37 

hanstan:
20170406 16:50:46
Touchdown 0.00s lol. All hail fastio :D 

looser69:
20170405 22:57:41
hurrah...easy one ...accepted in one go.. 
Added by:  Jamil Siam 
Date:  20170404 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 