[Spoj 5971] LCMSum

给定正整数 $n$，计算

$$\operatorname{LCM}(1,n)+\operatorname{LCM}(2,n)+\cdots+\operatorname{LCM}(n,n),$$

其中，$\operatorname{LCM}(i,n)$ 表示整数 $i$ 与 $n$ 的最小公倍数。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

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

输出格式

输出 $T$ 行。对于每个测试用例，输出一行一个整数，表示所求的最小公倍数之和。

样例输入

3
1
2
5

样例输出

1
4
55

数据范围

• $1\le T\le 3\times 10^5$；
• $1\le n\le 10^6$。

来源与许可

本题为 SPOJ 5971「LCMSum」，题面与测试数据整理自 BZOJ 2226。

样例 1

输入

3
1
2
5

输出

1
4
55