Problem Description

Two years ago, Silver187 learned Mobius inversion and knew how to calculate ($1\le n\le 10^9$)
$$
\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)
$$
One year ago, Silver187 learned how to calculate ($1\le n\le 10^5$)
$$
\sum_{i=1}^n \sum_{j=1}^n \varphi(ij)
$$
But he tried to solve this problem when $1\le n\le 10^9$. Finally, he failed to solve it. But he didn't completely fail, he solved a similar problem:

Silver187 defines that if $n=\prod_{i=1}^k p_i^{\alpha_i}(p_i\in \operatorname{prime} ,\alpha_i\gt0, \forall i \ne j, p_i \ne p_j)$ , then $H(n)=\prod_{i= 1}^k p_i$. In particular, $H(1)=1$.

Silver187 likes gcd, so he wants to ask you to calculate the result of the following formula.
$$
(\sum_{i=1}^n \sum_{j=1}^n H(ij)[\gcd(i,j)=1])\bmod 10^9+7
$$
Now, Silver187 asks you to solve this problem.

Input

First line has one integer $T(1≤T≤5)$, indicating there are $T$ test cases. In each case:

Only one line contains an integer $n(1\le n\le 10^9)$.

Input guarantee $\sum n\le 2\times 10^9$.

Output

In each case, output an integer on a line.

5
3
5
1000
10000
1000000

23
119
181591410
452132610
74649566