AABCC

题目描述

有多少个不超过 $N$ 的正整数可以表示为 $a^2 \times b \times c^2$,其中 $a,b,c$ 为满足 $a \lt b \lt c$ 的三个质数?

输入格式

输入按以下格式从标准输入给出:

$N$

输出格式

输出答案(一个整数)。

样例

1000

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$

1000000000000

2817785

数据范围

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