陶陶的难题I

时间限制:10s      空间限制:128MB

题目描述

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

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


输入格式

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


输出格式

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


样例输入

7 
1 
10 
100 
1000 
10000 
100000 
1000000 


样例输出

1
2127
18446224
183011304660
1827127167830060
18269345553999897648
182690854273058293758232


提示

没有写明提示


题目来源

没有写明来源

Menuappsclose