Chiaki 对一个无穷序列 $a_1, a_2, a_3, \dots$ 感兴趣，该序列定义如下：

$$a_n = \begin{cases} n & n \le 2 \\ 2 \cdot a_{n-1} & n \text{ 为奇数} \\ a_{n-1} + r_{n-1} & n \text{ 为偶数} \end{cases}$$

其中 $r_n$ 是不在集合 $S_n = \{a_j - a_i \mid 1 \le i < j \le n\}$ 中的最小正整数。

Chiaki 想知道该序列前 $n$ 项的和，即 $\sum_{i=1}^{n} a_i$。由于这个数字可能非常大，Chiaki 只对它对 $(10^9 + 7)$ 取模后的结果感兴趣。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n < 10^{100}$)，且不含前导零。

输出格式

对于每组测试数据，输出一个整数表示答案。

样例

样例输入 1

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

样例输出 1

1
3
7
15
31
52
94
145
247
359
834069170