8552: Yet Another Easy Function Sum Problem

Two years ago, Silver187 learned Mobius inversion and knew how to calculate 

∑nj=1∑ni=1gcd(i,j)

One year ago, Silver187 learned how to calculate 

∑nj=1∑ni=1φ(ij)

But he tried to solve this problem when 1≤n≤109. Finally, he failed to solve it. But he didn't completely fail, he solved a similar problem:

Silver187 defines that if

n=∏i=1kpiαi(pi∈prime,αi>0,∀i！=j,pi！=pj) ,

 then H(n)=∏i=1kpi. In particular, H(1)=1.

Silver187 likes gcd, so he wants to ask you to calculate the result of the following formula.

(i=1∑nj=1∑nH(ij)[gcd(i,j)=1])mod109+7

Now, Silver187 asks you to solve this problem.

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

Only one line contains an integer n(1≤n≤109).

Input guarantee ∑n≤2×109.

5
3
5
1000
10000
1000000

23
119
181591410
452132610
74649566