bzoj#P2401. 陶陶的难题I

陶陶的难题I

题目描述

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

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

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

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

输入格式

第一行包含一个正整数 TT ,表示有 TT 组测试数据。 接下来 TT 行,每行给出一个正整数 NN

输出格式

包含 TT 行,依次表示相应答案。

7
1
10
100
1000
10000
100000
1000000
1
2127
18446224
183011304660
1827127167830060
18269345553999897648
182690854273058293758232

数据规模与约定

对于 100%100\% 的数据,保证 T105,N106T\le 10^5 , N\le 10^6