版权声明

本题版权归 所有。

题目描述

给定一个整数 $n$，请你找到所有满足以下条件的质数三元组 $(a,b,c)$：

• $a,b,c$ 都是质数；
• $a<b<c$；
• 满足不等式：$[a^2×b×c^2≤n]$

请你计算共有多少组不同的 $(a,b,c)$ 可以满足以上条件。

输入格式

一行包含一个整数 $n$。

输出格式

一个整数，表示满足条件的三元组的个数。

输入输出样例

300

1

50000

72

说明/提示

对于 $40\%$ 的数据：$3×10^2≤n≤10^4$；
对于 $100\%$ 的数据：$3×10^2≤n≤9×10^5$。