D - AABCC Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

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

制約

  • N は 300 \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