L. Largest Prime Factor
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is Mango's dark history.

One day, he learned about the linear sieve, an algorithm capable of computing multiplicative functions, such as $$$\phi(n)$$$ and $$$\mu(n)$$$, in linear time. However, when explaining this algorithm to his teammates, he made a silly mistake. He confused the abbreviation LPF with Largest Prime Factor, as it is quite natural for a non-native English speaker to mistake least for largest.

To ensure he never forgets this embarrassing moment, he brings this problem to you. Given an integer $$$r$$$, calculate $$$$$$ \sum_{i=1}^r G(i) $$$$$$ where $$$G(i)$$$ denotes the largest prime factor of $$$i$$$. He uses the letter $$$G$$$ because it is more common to call it Greatest Prime Factor.

For convenience, define $$$G(1) = 0$$$.

Input

The only line of input contains a single integer $$$r$$$.

  • $$$1 \le r \le 10^{10}$$$
Output

Output a single integer representing the value of $$$\displaystyle \sum_{i=1}^r G(i)$$$.

It is guaranteed that the answer fits within a standard signed 64-bit integer.

Examples
Input
5
Output
12
Input
11
Output
43
Note

In the first sample, $$$\displaystyle \sum_{i=1}^5 = G(1) + G(2) + G(3) + G(4) + G(5) = 0 + 2 + 3 + 2 + 5 = 12$$$.

In the second sample, $$$\displaystyle \sum_{i=1}^{11} = 0 + 2 + 3 + 2 + 5 + 3 + 7 + 2 + 3 + 5 + 11 = 43$$$.