题目描述

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

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

输入格式

输入一个数 $N$。

输出格式

输出答案。

250

2

123456789012345

226863

数据范围

$1 \le N \le 10^{18}$