时空限制

时间限制 $1\text{s}$，内存限制 $512\text{MB}$。

题目描述

给定正整数 $n$，求同时满足以下条件的三元组 $(a,b,c)$ 个数：

1. $a,b,c$ 均为质数。
2. $2 \leq a < b < c$。
3. $a^2 \times b \times c^2 \leq n$。

输入格式

输入包含一行，给定一个正整数，表示 $n$。

输出格式

输出包含一行，输出一个整数，表示答案。

输入样例1

980

样例输出1

3

样例解释1

满足条件的数有 $300=2^2 \times 3 \times 5^2$，$588=2^2 \times 3 \times 7^2$，$980=2^2 \times 5 \times 7^2$。

输入样例2

1000000000000

输出样例2

2817785

数据范围

对于 $20\%$ 的数据，$1 \leq n \leq 10^3$。

对于 $80\%$ 的数据，$1 \leq n \leq 10^9$​​。

对于 $100\%$ 的数据，$1 \leq n \leq 10^{12}$。​