← 返回题目列表

Codeforces · 665/F

F. 四除数

中文机器翻译题面 查看原题

如果一个整数 a 可以被另一个整数 b 整除,则 b 称为 a 的约数。

例如:12 有 6 个正因数。它们是 1、2、3、4、6 和 12。

让我们定义一个函数 D(n) — 1 到 n(含)之间的整数个数,它恰好有四个正除数。

在 1 和 10 之间,只有整数 6、8 和 10 恰好有四个正因数。所以,D(10) = 3。

给定一个整数 n。您必须计算 D(n)。

输入

唯一一行包含整数 n (1 ≤ n ≤ 1011) — 问题陈述中的参数。

输出

打印唯一的整数 c — 1 到 n 之间正好有四个除数的整数的数量。

示例

输入 #1

10

输出 #1

3

输入 #2

20

输出 #2

5