250 相似数

题目描述

将满足以下条件的整数 $k$ 视为「与 250 相似」：

$k$ 可以表示为 $k=p \times q^3$，其中 $p \lt q$ 且 $p, q$ 均为素数。

求不超过 $N$ 的「与 250 相似」的整数有多少个。

输入格式

输入按以下格式从标准输入给出：

N

输出格式

将答案作为整数输出。

样例

250

2

$54 = 2 \times 3^3$ 与 250 相似。

$250 = 2 \times 5^3$ 与 250 相似。

上述两个整数是所有「与 250 相似」的整数。

1

0

123456789012345

226863

数据范围

• $N$ 是介于 $1$ 和 $10^{18}$（含）之间的整数。