LCM Sum#5141
Sign in

LCM Sum

1 second
128 megabytes
Medium
\mathrm{LCM}(1, n) + \mathrm{LCM}(2, n) + \dots + \mathrm{LCM}(n, n)

Given a positive integer , calculate the sumwhere \mathrm{LCM}(i, n) denotes the least common multiple of the integers and .

Input

The first line contains the number of test cases (1 \le t \le 300\,000). Each of the next lines contains an integer (1 \le n \le 10^6).

Output

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

Examples

Example 1

Loading
Loading