题目描述

在不大于N的正整数中，有多少个可以表示为$a^2 \times b \times c^2$的形式？其中$a$、$b$、$c$是满足$a < b < c$的质数。

输入格式

仅一行，包含一个整数(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

提示

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