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 105).
For each test case, there is only one line contains one number n(1≤n≤105).
1 2 3 4 5
0 1 2 4 5