You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

质数，即大于 $1$ 的，除了 $1$ 和本身之外不能被其他自然数整除的数。

• 呆呆熊 喜欢质数，对于一个质数 $x$ 来说，$2\sim (x-1)$ 之间一个因子也没有，非常安静。
• 与之相对，呆呆熊 认为一个数 $x$ 如果在 $2\sim (x-1)$ 之间有且只有两个因子。那么这就是一个喧闹数。

例如： $35=5*7$ 在$2\sim 9$ 之间有两个因数分别为5、7； $10=2*5$ 在$2\sim 9$ 之间有两个因数分别为2、5； $4=2*2$ 在$2\sim 9$ 之间有两个因数分别为2、2； $9=3*3$ 在$2\sim 9$ 之间有两个因数分别为3、3；

现在 呆呆熊 想要消灭 $1\sim n$ 以内的所有喧闹数。请你帮他数数，一共有几个。

输入格式

一个数 $n$。

输出格式

输出 $1\sim n$ 之内有几个喧闹数。

33

11

333

106

33333

8235

6666666

1290635

样例不解释，自己打表。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 10^7$。

• 子任务 1（10 分）：$n=50$
• 子任务 2（20 分）：$n\le 10^5$
• 子任务 3（30 分）：$n=3333333$
• 子任务 4（40 分）：没有特殊限制