题目描述

最近陶陶在研究数论，某天他偶然遇到一道题：对于给定的正整数 $N$ ，求出下面这样一个式子的值：

$$\sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \operatorname{lcm}(i,j) $$

其中 $\operatorname{lcm}(x,y)$ 表示正整数 $x$ 和 $y$ 最小公倍数，即能同时被 $a$ 和 $b$ 整除的最小正整数。

作为神犇的陶陶，当然轻松秒杀了这道题。不过他希望你写一个程序，用来检验他算的答案是否正确。

输入格式

第一行包含一个正整数 $T$ ，表示有 $T$ 组测试数据。 接下来 $T$ 行，每行给出一个正整数 $N$ 。

输出格式

包含 $T$ 行，依次表示相应答案。

7
1
10
100
1000
10000
100000
1000000

1
2127
18446224
183011304660
1827127167830060
18269345553999897648
182690854273058293758232

数据规模与约定

对于 $100\%$ 的数据，保证 $T\le 10^5 , N\le 10^6$ 。