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

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

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.

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

1000000000000

2817785