MAXGRITH - Maximum Girth

no tags 

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 N-vertices and (N+1) edges could possibly 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 separate line.

Example

Input:
3
45
3434
5656565

Output:
30
2290
3771044

Constraints

1 <= T <= 1000

1 <= N <= 10^18


hide comments
:D: 2015-03-13 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: 2014-06-16 13:25:45

very tough -_- :P

Vipul Pandey: 2014-01-05 21:50:49

great problem.

olimpoUS: 2013-07-27 18:42:40

What About?
3
1
2
3
???????

Peutri: 2013-06-16 17:45:35

I just got AC on first try without even understanding the problem. Hate it when that happens.

[Lakshman]: 2013-06-06 15:16:00

@Thanks Ouditchya Sinha got AC.
A Silly mistake cause 2 WA.

Last edit: 2013-06-06 16:25:11
[Lakshman]: 2013-06-01 12:02:30

AC..

Last edit: 2013-06-06 15:17:50
shiva_hellgeek: 2013-05-31 00:03:55

Excellent problem...
Spent the entire night trying to figure it out... :D

raunakrocks: 2013-05-28 10:32:37

nyce :P


Added by::(){ :|: & };:
Date:2013-05-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64