配点 : $400$ 点

問題文

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

制約

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

入力

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

$N$

出力

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

1000

3

$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$

1000000000000

2817785