题目描述

请问有多少个不大于 $N$ 的正整数，可以表示为 $a^2 \times b \times c^2$ 的形式？

其中 $a, b, c$ 必须是满足 $a < b < c$ 的三个质数。

输入格式

输入仅包含一行，一个正整数 $N$。

输出格式

输出一行，一个整数，表示满足条件的正整数的个数。

样例输入 1

1000

样例输出 1

3

样例输入 2

1000000000000

样例输出 2

2817785

说明

样例解释

在第一个样例中，不大于 $1000$ 且满足条件的正整数共有以下 $3$ 个：

• $300 = 2^2 \times 3 \times 5^2$
• $588 = 2^2 \times 3 \times 7^2$
• $980 = 2^2 \times 5 \times 7^2$

数据范围

本题共 $10$ 个测试点。

• 对于测试点 $1$，保证 $1 \le N \le 100$。
• 对于测试点 $2 \sim 4$，保证 $101 \le N \le 500$。
• 对于测试点 $5 \sim 7$，保证 $1 \le N \le 10^6$。
• 对于测试点 $8 \sim 10$，保证 $1 \le N \le 10^{12}$。
• 对于所有测试点，保证输入值 $N$ 为正整数。