两年前，Silver187 学习了莫比乌斯反演，并学会了如何计算 ($1 \le n \le 10^9$)： $$\sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i, j)$$

一年前，Silver187 学会了如何计算 ($1 \le n \le 10^5$)： $$\sum_{i=1}^{n} \sum_{j=1}^{n} \varphi(ij)$$

但他尝试解决 $1 \le n \le 10^9$ 的情况时失败了。不过他并没有完全失败，他解决了一个类似的问题： Silver187 定义，若 $n = \prod_{i=1}^{k} p_i^{\alpha_i}$（其中 $p_i$ 为质数，$\alpha_i > 0$，且对于任意 $i \neq j$，$p_i \neq p_j$），则 $H(n) = \prod_{i=1}^{k} p_i$。 Silver187 喜欢 $\gcd$，所以他想请你计算以下公式的结果： $$\left( \sum_{i=1}^{n} \sum_{j=1}^{n} H(ij)[\gcd(i, j) = 1] \right) \pmod{10^9 + 7}$$

现在，Silver187 请你解决这个问题。

输入格式

第一行包含一个整数 $T(1 \le T \le 5)$，表示测试用例的数量。每个测试用例： 仅一行，包含一个整数 $n(1 \le n \le 10^9)$。 输入保证 $n \le 2 \times 10^9$。

输出格式

对于每个测试用例，输出一行一个整数。

样例

样例输入 1

5
3
5
1000
10000
1000000

样例输出 1

23
119
181591410
452132610
74649566