[Spoj 5971] LCMSum

时间限制:20s      空间限制:259MB

题目描述

Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.


输入格式

The first line contains T the number of test cases. Each of the next T lines contain an integer n.


输出格式

Output T lines, one for each test case, containing the required sum.


样例输入

3
1
2
5


样例输出

1
4
55

提示

Constraints 1 <= T <= 300000 1 <= n <= 1000000


题目来源

没有写明来源