题目描述

如果一个整数 $k$ 满足：存在素数 $p$ 和 $q$ 使得 $p<q,k=p\times q^3$，则称 $k$ 为 与 $250$ 相似的数。

现在给出一个数 $N$，请求出小于 $N$ 的 与$250$相似的数 一共有几个。

输入格式

输入一个整数 $N$

输出格式

输出一共有几个符合条件的数字

250

2

1

0

123456789012345

226863

样例 1 解释

• $54 = 2 \times 3^3$ 是 与 $250$ 类似。
• $250 = 2 \times 5^3$ 是 与 $250$ 类似。

以上两个整数是所有 与 $250$ 类似 的整数。

提示

• $1\leq N \leq 10^{18}$