Contest Duration: - (local time) (100 minutes) Back to Home
D - AABCC /

Time Limit: 3 sec / Memory Limit: 1024 MB

### 問題文

N 以下の正整数のうち、 a<b<c なる 素数 a,b,c を用いて a^2 \times b \times c^2 と表せるものはいくつありますか?

### 制約

• N300 \le N \le 10^{12} を満たす整数

### 入力

N


### 入力例 1

1000


### 出力例 1

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

### 入力例 2

1000000000000


### 出力例 2

2817785


Score : 400 points

### Problem Statement

How many positive integers no greater than N can be represented as a^2 \times b \times c^2 with three primes a,b, and c such that a<b<c?

### Constraints

• N is an integer satisfying 300 \le N \le 10^{12}.

### Input

The input is given from Standard Input in the following format:

N


### Output

Print the answer as an integer.

### Sample Input 1

1000


### Sample Output 1

3


The conforming integers no greater than 1000 are the following three.

• 300 = 2^2 \times 3 \times 5^2
• 588 = 2^2 \times 3 \times 7^2
• 980 = 2^2 \times 5 \times 7^2

### Sample Input 2

1000000000000


### Sample Output 2

2817785