题目描述

给定一个正整数 $N$，找出不大于 $N$ 的正整数中，可以写成 $a^2 \times b \times c^2$ 的形式的数的个数，其中 $a,b,c$ 是三个质数，并且满足 $a<b<c$。

约束条件

• $N$ 是满足 $300 \le N \le 10^{12}$ 的整数。

输入

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

$N$

输出

输出一个整数，表示满足条件的数的个数。

示例输入 1

1000

示例输出 1

3

不大于 $1000$ 的满足条件的整数有以下三个：

• $300 = 2^2 \times 3 \times 5^2$
• $588 = 2^2 \times 3 \times 7^2$
• $980 = 2^2 \times 5 \times 7^2$

示例输入 2

1000000000000

示例输出 2

2817785