Problem Description

For a positive integer $ n $, let $ f(n) $ be the number of prime factors of $ n $ counted with multiplicity. For example, since $200 = 2^3 \times 5^2$, we have $ f(200) = 5 $.

Given a positive integer $ N $, find $\sum_{n=1}^N f(n)$.

Input Format

$ N $

Output Format

Output the value of $\sum_{n=1}^N f(n)$ in one line.

Sample Input and Output

Sample Input #1

6

Sample Output #1

7

Sample Input #2

2019

Sample Output #2

6028

Sample Input #3

906150257

Sample Output #3

3660251364

Notes/Hints

Constraints

• $1 \le N \le 10^{11}$.

Partial Points

• If you correctly solve the dataset where $N \le 10^{10}$, you will be awarded 45 points.
• If you correctly solve the dataset without additional constraints, you will be awarded an additional 55 points.

Sample Explanation 1

$ f(1) = 0 $, $ f(2) = 1 $, $ f(3) = 1 $, $ f(4) = 2 $, $ f(5) = 1 $, $ f(6) = 2 $, so the answer is $ 0 + 1 + 1 + 2 + 1 + 2 = 7 $.

见题面 Input 部分

见题面 Output 部分