题目描述

求满足$1< p \leq n$ 且 $p$ 的二进制表示最后两位为 $01$ 的质数 $p$ 有多少个。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数 $\pi$ 表示答案。

样例 1

input

20

output

3

质数 $5,13,17$ 满足要求。

样例 2

input

100000

output

4783

数据范围与提示

对于 $30\%$ 的数据，$1\leq n\leq 10^4$

对于 $50\%$ 的数据，$1\leq n\leq 10^7$

对于 $80\%$ 的数据，$1\leq n\leq 10^{10}$

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^{10}$