Semiprime

であり、 は つの素数の積として表すことができます。
このように、 つの（同じであってもよい）素数の積として表せる正整数を半素数といいます。
以上 以下の整数のうち、半素数はいくつありますか？

• 入力はすべて整数

N

計算結果を一行に出力せよ。

10

4

以下の正整数であって、半素数であるものは の つです。
例えば、 は つの素数 を用いて、 として表せます。
つの素数が同じであってもよいです。

5000

1365