#2401. 陶陶的难题I

题目描述

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

其中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  

数据范围与提示