GCD Tree

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.

1
2
3
4
5

0
1
2
4
5

xudyh

2015 Multi-University Training Contest 9