Problem Description

$\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n [(i,j),(k,l)]$

Input

First line contains a single integer $T \leq 100$ which denotes the number of test cases.

For each test case, there is an positive integer $n \leq 10^{7}$.

Output

For each case, output an integer in a single line means the answer mod $2^{32}$.

1
1

1

Hint

[a,b] means lowest common multiple of a and b,(a,b) means greatest common divisor of a and b.