A quasiperfect number is a positive integer $n$ where the sum of all its divisors is equal to $2n + 1$.

Given an integer $M$, count the number of quasiperfect numbers between $1$ and $M$ inclusive (including both endpoints).

Input

The only line of input contains an integer $M$.

Output

Output the number of quasiperfect numbers in the required range.

Constraints

Subtask 1 (70%): $1 \le M \le 1000$
Subtask 2 (30%): $1 \le M \le 10^6$