UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2401. 陶陶的难题I

统计 下载数据

Description

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

其中LCM(a???, b???)表示正整数???和???最小公倍数,即能同时被a???和b???整除的最小正
整数。
作为神犇的陶陶,当然轻松秒杀了这道题。不过他希望你写一个程序,用来
检验他算的答案是否正确。

Input

第一行包含一个正整数???T,表示有T???组测试数据。接下来???T<=10^5
行,每行给出一个正整数N,N<=10^6。

Output

包含T???行,依次给出对应的答案。

Sample Input

7
1
10
100
1000
10000
100000
1000000

Sample Output

1
2127
18446224
183011304660
1827127167830060
18269345553999897648
182690854273058293758232

Hint

Source