GCD Tree

Problem Description

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.

Input

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)$.

Output

For each test case, print the answer.

Sample Input

1
2
3
4
5

Sample Output

0
1
2
4
5

Author

xudyh

Source

2015 Multi-University Training Contest 9