Migrated from Lutece 2497 An Easy Math Problem II

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

给定 $n$ 这个正整数，计算下式的值

$\gcd(i,j)$ 表示 $i$ 与 $j$ 的最大公约数。

$\varphi(x)$ 表示 $1$ 到 $x$ 中与 $x$ 互质的数的个数，即 $\varphi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1]$。

Input

第一行有一个正整数 $t\ (1\le t \le 5000)$。

下面有 $t$ 组测试用例，每个测试用例包含一个正整数 $n\ (1\le n\le 10^7)$。

Output

对于每个测试用例，输出一个整数表示该式子对 $10^9+7$ 的取模后的值。

Samples

3
1
2
3

1
9
45

Resources

2020 UESTC ICPC Training for Math and Geometry