問題文

$N$ 頂点の重み付き無向完全グラフ $G$ があり、 $G$ の各頂点には $1$ から $N$ の番号が付けられています。

$G$ の頂点 $i$ と頂点 $j(i < j)$ を結ぶ辺の重みは $\gcd(i,j)$ 、つまり $i$ と $j$ の最大公約数です。

$dist(x,y)$ を、頂点 $x$ からいくつかの辺を辿って頂点 $y$ へ移動するときに辿る辺の重みの総和の最小値とします。

$\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} dist(i,j)$ を求めてください。なお、制約の条件下で答えは $2^{63}$ 未満であることが保証されます。

$1$ つの入力ファイルにつき $T$ 個のテストケースに答えてください。

入力

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

$N$

• $1\le T \le 2×10^5$
• $2\le N\le 10^7$
• 入力はすべて整数

出力

答えを出力してください。 $i$ 行目には $i$ 個目のテストケースに対する答えを出力してください。

サンプル

3
2
4
10000000

1
7
69603633572759