L. Chiaki Sequence
time limit per test
5 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

Chiaki is interested in an infinite sequence a1, a2, a3, ..., which defined as follows:

where rn is the smallest positive integer not in the set Sn = {aj - ai|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 (109 + 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 < 10100) without leading zeros.

Output

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

Example
Input
11
1
2
3
4
5
6
7
8
9
10
1000000000
Output
1
3
7
15
31
52
94
145
247
359
834069170