Migrated from Lutece 1954 GCD Tree

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Captain Qin has a graph with $n$ vertices numbered from $1$ to $n$. For every $\mathrm{edge}(u, v)$, the weight is $\mathrm{gcd}(u, v)$. ($\mathrm{gcd}(u, v)$ means the greatest common divisor of number $u$ and $v$).

You need to find a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is maximized. Print the total weight of these edges.

Input

First line of the input contains one integer $T$ ($1 \le T \le 10^5$) — numbef of test cases

For each test case, there is only one line containing one integer $n$ ($1 \le n \le 10^5$).

Output

For each test case, print one integer — the answer.

Samples

5
1
2
3
4
5

0
1
2
4
5

Resources

每周一题 div1