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

Input:
3
1
2
5
Output:
1
4
55

Constraints

1 ≤ T ≤ 300000
1 ≤ n ≤ 1000000