×

# 计蒜客

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