Problem Statement

There is a weighted undirected complete graph $G$ with $N$ vertices, and the vertices of $G$ are numbered from $1$ to $N$.

The weight of the edge connecting vertex $i$ and vertex $j(i < j)$ of $G$ is $\gcd(i,j)$, that is, the greatest common divisor of $i$ and $j$.

Let $dist(x,y)$ be the minimum total weight of the edges traversed when moving from vertex $x$ to vertex $y$ by following some edges.

Find $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} dist(i,j)$. It is guaranteed that the answer is less than $2^{63}$ under the given constraints.

For $1$ input file, answer $T$ test cases.

Input

$T$
$case_1$
$case_2$
:
$case_T$

$N$

• $1\le T \le 2×10^5$
• $2\le N\le 10^7$
• All inputs are integers.

Output

Output the answers. On line $i$, output the answer to test case $i$.

Sample

3
2
4
10000000

1
7
69603633572759