×

- 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

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)$

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

3 2 4 6

30 1291 12715