Migrated from Lutece 2280 oy function

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

数学天才oy想到了一个函数，取名为oy function

$f(n)=\sum_{i=1}^{n}\sum_{j=1}^n \varphi(\gcd(i,j))$

其中$\varphi$为欧拉函数

现在oy想知道$f(n)$的值

Input

第一行为一个正整数$T$，表式数据组数

接下来$T$行，每行一个整数$n$

Output

$T$行，每行一个整数表示答案

Samples

1
10

136

Constraints

$T \le 5000,1 \le n \le 10^7$

Resources

2019 UESTC ACM Training for math and geometry