该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

故事背景：

在数字王国的深处，强哥发现了一座被称为质数神殿的古老遗迹。传说中，神殿的宝藏藏在一个神秘的数字组合里——这些数字可以写成特殊的形式：$a^{2} \times b \times c^{2}$，其中 $a, b, c$ 是不同的质数，且满足 $a < b < c$ 的条件。

强哥的任务是解开这个谜题：对于给定的整数 $N$，他需要找出在 $N$ 以内有多少个数字可以写成这种形式。

任务描述：

给定一个整数 $N$，帮助强哥统计在 $N$ 以内有多少数可以写成 $a^{2} \times b \times c^{2}$ 的形式，其中 $a, b, c$ 都是质数，并且满足 $a < b < c$。

强哥的目标是找到这些特殊数字的个数，解锁神殿中的宝藏！

限制

• $N$ 是满足 $300 \le N \le 10^{12}$ 的整数

输入格式

输入通过标准输入，格式如下。

N

输出格式

以整数形式输出答案。

1000

3

$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$

1000000000000

2817785