题目描述

对于一个大于 $1$ 的整数 $N$，如果 $N$ 是一个素数，则其约数只有 $1$ 和 $N$ 本身。换句话说，只有 $2$ 个约数的数就是素数。

例如，$2$、$3$、$5$、$7$、$11$、$13$ 等都是素数，而 $4$、$6$、$8$ 等不是素数。

现在我们定义一个数字为新素数，当且仅当其约数个数为 $4$ 个。例如，$8$、$15$ 等都是新素数，而 $1$、$4$ 等不是新素数。

现在给定你一个整数 $N$，请你判断在 $2 \sim N$ 这 $N-1$ 个整数中，有多少个是新素数。

输入格式

输入一行，包含一个整数 $N$，表示一个指定的整数。

输出格式

输出一行，包含一个整数，表示在 $2 \sim N$ 这 $N-1$ 个整数中，有多少个是新素数。

样例输入 1

24

样例输出 1

7

样例输入 2

11451

样例输出 2

2975

说明

数据范围

• 对于 $40\%$ 的数据，保证 $1 \le N \le 500$。
• 对于 $70\%$ 的数据，保证 $1 \le N \le 5000$。
• 对于 $100\%$ 的数据，保证 $1 \le N \le 100000$。