题目描述

满足以下条件的整数 $k$ 被称为“250 类似数”。

• 存在素数 $p < q$，使得 $k = p \times q^3$。

请问不超过 $N$ 的“250 类似数”共有多少个？

输入格式

输入为以下格式，从标准输入读取。

$N$

输出格式

请输出答案，结果为一个整数。

样例 1

输入

250

输出

2

样例 2

输入

1

输出

0

样例 3

输入

123456789012345

输出

226863

说明/提示

限制条件

• $N$ 是一个满足 $1 \leq N \leq 10^{18}$ 的整数。

样例解释 1

• $54 = 2 \times 3^3$，因此是“250 类似数”。
• $250 = 2 \times 5^3$，因此是“250 类似数”。 不超过 $250$ 的“250 类似数”有上述 $2$ 个。

由 ChatGPT 4.1 翻译