SPOJ (BNUOJ) LCM Sum

Time Limit: 5000 ms     Case Time Limit: 5000 ms     Memory Limit: 262144 KB

Submit: 4     Accepted: 0

This problem will be judged on SPOJ. Original ID: LCMSUM.

[Prev][Next]

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.

Example

Sample Input :

3

1

2

5

Sample Output :

4

55

Constraints

1 <= T <= 300000

1 <= n <= 1000000