一行一个整数 $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​​