求各位大佬，给点思路

求有多少个不同的正整数 p，使得 p 同时满足如下条件：

(1) p <= N,其中 N 是读入的整数。

(2) p = x * x* y * z * z，其中 x,y,z 都是质数，且 x < y < z。

【输入格式】

一个整数 n， 3<=n<=10^12。

【输出格式】

一个整数。

【输入样例 1】

1000

【输出样例 1】

3

【输入样例 2】

1000000000000

【输出样例 2】

2817785

【样例解释】 样例一解释： 300=2^235^2

588=2^237^2

980=2^257^2