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

For each test case, there is only one line contains one number n(1≤n≤105).

Output:

For each test case, print the answer.

Sample Input:

1 2 3 4 5

Sample Output:

0 1 2 4 5

Source:

Submit