Teacher Mai has a graph with $n$ vertices numbered from $1$ to $n$. For every edge($u$,$v$), the weight is gcd($u$,$v$). (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.
There are multiple test cases(about $10^5$).
For each test case, there is only one line contains one number $n(1\leq n\leq 10^5)$.
For each test case, print the answer.