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 (1 ≤ t ≤ 300000). Each of the next t lines contains an integer n (1 ≤ n ≤ 106).

Output

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