该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

我们称一个整数$k$为“幸运数”，如果满足以下条件：

• $k$可以表示为$k = p \times q^3$，其中$p$和$q$为质数且$p < q$。 问有多少个小于等于$N$的整数是“幸运数”？

约束条件

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

输入

输入通过标准输入给出，格式如下：

N

输出

输出一个整数作为答案。

样例输入1

250

样例输出1

2

• $54 = 2 \times 3^3$是“幸运数”。
• $250 = 2 \times 5^3$是“幸运数”。 以上两个整数是所有满足条件的“幸运数”。

样例输入2

1

样例输出2

0

样例输入3

123456789012345

样例输出3

226863