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