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⁹+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⁹+7) in a separate line.

Example

Input:
3
45
3434
5656565

Output:
30
2290
3771044

Constraints

1 ≤ T ≤ 1000

1 ≤ N ≤ 10¹⁸