Unexpressed

One integer $n$ is given. How many integers between $1$ and $n$ (inclusive) are unrepresentable as $a^b$, where $a$ and $b$ are integers not less than $2$?

Input

One positive integer $n(n\le 10^{10})$.

Output

Print the amount of unrepresentable numbers.

Examples