MAXGRITH  Maximum Girth
In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph. Can you find the maximum girth a graph with Nvertices and (N+1) edges could possible have?
Since the answer could be large output the answer modulo 10^9+7.
Input
The first line contains single integer T  the number of test cases. Each of the next T lines contains a single integer N.
Output
For every test case output the maximum girth (modulo 10^9+7) in a seperate line.
Example
Input:
3 45 3434 5656565Output:
30 2290 3771044
Constraints:
1 <= T <= 1000
1 <= N <= 10^18
hide comments
:D:
20150313 21:18:37
For N <= 3 I printed "0" as the result. Don't know if those values are actually used in test cases. 

Rishav Goyal:
20140616 13:25:45
very tough _ :P 

Vipul Pandey:
20140105 21:50:49
great problem. 

olimpoUS:
20130727 18:42:40
What About?


Peutri:
20130616 17:45:35
I just got AC on first try without even understanding the problem. Hate it when that happens. 

[Lakshman]:
20130606 15:16:00
@Thanks Ouditchya Sinha got AC.


[Lakshman]:
20130601 12:02:30
AC.. Last edit: 20130606 15:17:50 

shiva_hellgeek:
20130531 00:03:55
Excellent problem...


raunakrocks:
20130528 10:32:37
nyce :P 
Added by:  :(){ :: & };: 
Date:  20130516 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 