题目描述

$N$ 以下の正整数のうち、 $a\ <\ b\ <\ c$ なる 素数 $a,b,c$ を用いて $a^2\ \times\ b\ \times\ c^2$ と表せるものはいくつありますか?

输入格式

入力は以下の形式で標準入力から与えられる。

$N$

输出格式

答えを整数として出力せよ。

题目大意

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

1000

3

1000000000000

2817785

提示

制約

• $N$ は $300\ \le\ N\ \le\ 10^{12}$ を満たす整数

Sample Explanation 1

$1000$ 以下で条件を満たす整数は以下の $3$ つです。 - $300\ =\ 2^2\ \times\ 3\ \times\ 5^2$ - $588\ =\ 2^2\ \times\ 3\ \times\ 7^2$ - $980\ =\ 2^2\ \times\ 5\ \times\ 7^2$