Migrated from Lutece 621 吴神的大脑

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

下面是吴神随手写的一段代码

G=0;
for (int i = 1; i < N; i++) {
  for (int j = i + 1; j <= N; j++) {
    G += gcd(i, j);
  }
}

反正以吴神的大脑能在$h$(量子物理里面的一个常量，你猜？)秒内跑出答案，现在看看你的大脑跑得出答案不？？

Input

第一行有个整数$T$，代表数据组数（$T\leq 100$）

接下来有$T$行，每行有个整数$N$ ($N<1000000$)

Output

输出$T$行，每行输出一个整数$G$代表对应$N$的程序运行的结果

Samples

3
10
20
100000

67
335
33717147452

Resources

UESTC Training for Math