Migrated from Lutece 2405 Fou ki ra

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

——KOKIA - EXEC_COSMOFLIPS/.

这个屑出题人暂时不想写小说了，所以就直接读题吧（

---

令 $B_{i,j}=\binom{2i}{j}$，$F_i$ 为斐波那契数列第 $i$ 项; 同时，令 $A_i$ 表示一个序列，$A_i = \{B_{i,1},B_{i,3},B_{i,5},\ldots ,B_{i,2i-1}\}$。

设序列

$${F_{A_i}=\{F_{B_{i,1}},F_{B_{i,3}},F_{B_{i,5}},\ldots ,F_{B_{i,2i-1}}\}}\\ {\gcd(F_{A_i})=\gcd(F_{B_{i,1}},F_{B_{i,3}},F_{B_{i,5}},\ldots ,F_{B_{i,2i-1}})} $$

求 $\sum\limits_{k=1}^{n}\gcd (F_{A_k}) \bmod 10^9+7$。

Input

第一行一个整数 $T$，表示一共有 $T$ 组数据。

接下来 $T$ 行，每一行一个整数 $n$。

Output

输出 $T$ 行，每一行为一组数据的答案。

Samples

3
2
3
4

4
5
26

Constraints

$1 \le T \le 5\times 10^5,\ 2\le n\le 10^9$

Resources

2020 UESTC ICPC Training for Math and Geometry