×

计蒜客

  1. 题库
  2. tsy's number
  3. 问答
  • 21.29%
  • 2000ms
  • 262144K

Tsy as a math enthusiast and the favorite thing is to get the sum of function, one day he was studying the Euler function, while writing a formula

$$\displaystyle \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\frac {φ(i)φ(j^2)φ(k^3)} {φ(i)φ(j)φ(k)}φ(gcd(i,j,k)) $$

After had written,tsy took it to his friend zxy for solution but zxy Zxy don't know any Math at all. As the friends of Zxy, can you help him ?

the result need to $2^{30}$ modulo

Input

multiple testcase

a single $T$ in the first line represents the number of groups $(T \le 10000)$ and $T$ lines follows each line has a number $n(1 \le n \le 10^7)$

Output

For each set of data, output a number to represent the result

样例输入

3
2
4
6

样例输出

30
1291
12715

想挑战这道题吗

  • main.c