J. Just Not RU...
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Arthur has night classes at UnB every day, so he has to have dinner before going to class. He knows that most people usually have dinner at the RU, and he has nothing against the RU, but he thinks life is too short to miss out on different gastronomic experiences... However, not all of his friends share this point of view, so it is necessary to convince them.

Arthur and his friends have already not eaten at the RU on day $$$1$$$, because "on the first day it is fine". But now his friends are determined to go to the RU in the next days. To prevent this, Arthur had an idea. He will propose the following: "we can go to the RU every day, just not on days that are multiples of $$$X$$$", such that $$$X$$$ is a positive integer larger than $$$1$$$. This seems reasonable to his friends at first, but little do they know that Arthur will choose several values of $$$X$$$ so that they never go to the RU from day $$$1$$$ to day $$$N$$$...

But Arthur must be careful so that his friends do not realize what he is doing! For this, he must say the smallest possible number of values $$$X$$$ — otherwise, it would be too suspicious and he would be dragged to the RU!

Help him, and compute the smallest possible number of values $$$X$$$ that Arthur must tell his friends so that they end up not going to the RU on any of the days from $$$1$$$ to $$$N$$$.

Input

The input consists of a single integer $$$N$$$: the number of days $$$(1 \leq N \leq 10^6)$$$.

Output

Print, on a single line, the smallest possible number of values $$$X$$$ that Arthur must tell his friends so that they end up not going to the RU on any of the days from $$$1$$$ to $$$N$$$.

Examples
Input
1
Output
0
Input
4
Output
2
Input
12
Output
5
Input
1000000
Output
78498
Note

In the first test case, since $$$N = 1$$$ and Arthur didn't go to the university restaurant on the first day, it's not necessary to tell any value for $$$X$$$.

In the second test case, Arthur can use $$$X = 2$$$ and $$$X = 3$$$ to not go on any of the $$$N = 4$$$ days (note that Arthur won't go on day $$$4$$$, because $$$4$$$ is a multiple of $$$2$$$).