e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Euler Function

LCM Sum

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

First line contains the number of test cases t (1t300000). Each of the next t lines contains an integer n (1n106).

Output

Print t lines, one for each test case, containing the required sum.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
1
2
5
Output example #1
1
4
55