UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2226. [Spoj 5971] LCMSum

Statistics 下载数据

Description

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.

Input

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

Output

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

Sample Input

3
1
2
5

Sample Output

1
4
55

Hint

Constraints

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

Source