Chiaki is interested in an infinite sequence a₁, a₂, a₃, ..., which defined as follows:

where r_n is the smallest positive integer not in the set S_n = {a_j - a_i | 1 ≤ i < j ≤ n}.

Chiaki would like to know the sum of the first n terms of the sequence, i.e. . As this number may be very large, Chiaki is only interested in its remainder modulo (10⁹ + 7).

Input

There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 1000), indicating the number of test cases. For each test case:

The first line contains an integer n (1 ≤ n < 10¹⁰⁰) without leading zeros.

Output

For each test case, output an integer denoting the answer.

Sample Input

11
1
2
3
4
5
6
7
8
9
10
1000000000

Sample Output

1
3
7
15
31
52
94
145
247
359
834069170

The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple