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 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
5656565
Output:

30
2290
3771044

Constraints:

1 <= T <= 1000
1 <= N <= 10^18