题目描述

给定一个整数 $N$，统计 $N$ 以内有多少数可以写成 $a^{2} \times b \times c^{2}$ 的形式？其中，$a, b, c$ 都是质数，且 $a < b < c$。

输入格式

一个数 $300\ \le\ N\ \le\ 10^{12}$。

输出格式

答案。

1000

3

1000000000000

2817785

提示

对于样例 $1$，$300,588,980$ 三个数满足题目要求。