题目描述

在不超过 $N$ 的正整数中，有多少个可以表示为 $a^2 \times b \times c^2$ 的数，其中 $a, b, c$ 均为素数，且满足 $a < b < c$？

输入格式

输入从标准输入中给出，格式如下：

$N$

输出格式

请输出满足条件的整数的个数。

样例 1

输入

1000

输出

3

样例 2

输入

1000000000000

输出

2817785

说明/提示

限制条件

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

样例说明 1

不超过 $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$

由 ChatGPT 4.1 翻译