F. Prime Precipitation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Paulina the Precipitation Princess is working on a very interesting new method of creating rain, which she has named "prime precipitation".

She has specially engineered raindrops with unique aerodynamic properties, where their fall speed depends on their height. Given a raindrop's height, every second it will fall by exactly the number of prime divisors it has. For example, a raindrop at a height of $$$12$$$ will fall to a height of $$$9$$$ (as $$$12$$$ is divisible by two twice and three once). A raindrop at a height of $$$10$$$ will fall to a height of $$$8$$$ (as $$$10$$$ is divisible by two and five).

Given that elevation $$$1$$$ is the ground, such a raindrop may fall to the ground in $$$5$$$ seconds ($$$10 \rightarrow 8 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1$$$).

For her first rainstorm, she will be dropping one raindrop of each height $$$[1, H]$$$. She will drop a raindrop, wait for it to hit the ground, then drop the next one.

Given this maximum height $$$H$$$, help Paulina determine how much time it will take for her to complete this process.

Input

A single integer, $$$H$$$ ($$$1 \leq H \leq 4 \cdot 10^6$$$).

Output

A single integer, the number of seconds for Paulina to drop all the rain.

Example
Input
6
Output
11
Note

You may need 64-bit integers for this problem.

Due to time limit constraints, this may be difficult to solve in Python.