Problem Description

ZHY has a complete graph with $n$ vertices, where the distance between vertex $u$ and vertex $v$ is $\gcd(u,v)$. Find the sum of the edge weights of the maximum spanning tree of this complete graph.

Input Format

A single positive integer $n$.

Output Format

A single integer representing the sum of the edge weights of the maximum spanning tree.

Sample Input and Output

Sample Input #1

4

Sample Output #1

4

Sample Input #2

30

Sample Output #2

183

Sample Input #3

100

Sample Output #3

1916

Notes

This problem uses batched testing.

$\text{Subtask}$ [MATH6]: $n \le 5$.

$\text{Subtask}$ [MATH9]: $n \le 1000$.

$\text{Subtask}$ [MATH12]: $n \le 10^{6}$.

$\text{Subtask}$ [MATH15]: $n \le 10^{7}$.

For all test cases, $1 \le n \le 10^{7}$.

见题面 Input 部分

见题面 Output 部分