题目描述

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

(1) $p \le N$ ,其中 $N$ 是读入的整数。

(2) $p = x \times x \times y \times z \times z$，其中 $x,y,z$ 都是质数，且 $x \lt y \lt z$。

输入格式

一个整数 $n$， $3 \le n \le 10^{12}$。

输出格式

一个整数。

样例

1000

3

样例解释 1

300=2*2*3*5*5

588=2*2*3*7*7

980=2*2*5*7*7

1000000000000

2817785