2531: #6027. 「from CommonAnts」质数计数 I

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

输入格式

一行一个整数 $n$。

输出格式

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

样例

样例输入 1

20

样例输出 1

3

样例解释 1

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

样例输入 2

100000

样例输出 2

4783

数据范围与提示

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

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

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

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