D - 250-like Number Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

以下の条件を満たす整数 k を「 250 に似た数」と呼びます。

  • k が素数 p<q を使って k=p \times q^3 と表される。

N 以下の「 250 に似た数」は全部でいくつありますか？

制約

  • N は 1 以上 10^{18} 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを整数として出力せよ。

入力例 1

250

出力例 1

2
  • 54 = 2 \times 3^3 なので、「 250 に似た数」です。
  • 250 = 2 \times 5^3 なので、「 250 に似た数」です。

250 以下の「 250 に似た数」は、以上の 2 つです。

入力例 2

1

出力例 2

0

入力例 3

123456789012345

出力例 3

226863

Score : 400 points

Problem Statement

Let us regard an integer k as "similar to 250" if the following condition is satisfied:

  • k is represented as k=p \times q^3 with primes p<q.

How many integers less than or equal to N are "similar to 250"?

Constraints

  • N is an integer between 1 and 10^{18} (inclusive)

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer as an integer.

Sample Input 1

250

Sample Output 1

2
  • 54 = 2 \times 3^3 is "similar to 250".
  • 250 = 2 \times 5^3 is "similar to 250".

The two integers above are all the integers "similar to 250".

Sample Input 2

1

Sample Output 2

0

Sample Input 3

123456789012345

Sample Output 3

226863