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$ 和本身之外不能被其他自然数整除的数。

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

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

输入格式

一个数 $n$。

输出格式

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

33

10

333

102

33333

8204

6666666

1290301

样例不解释，自己打表。

数据规模与约定

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

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