G - 9 Divisors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 以下の正整数のうち、正の約数をちょうど 9 個持つものの個数を求めてください。

制約

  • 1\leq N\leq 4\times 10^{12}
  • 入力される数値は全て整数

入力

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

N

出力

答えを出力せよ。

入力例 1

200

出力例 1

3

条件を満たす正整数は 36,100,196 の 3 個です。

入力例 2

4000000000000

出力例 2

407073

Score : 400 points

Problem Statement

Find the number of positive integers not greater than N that have exactly 9 positive divisors.

Constraints

  • 1 \leq N \leq 4 \times 10^{12}
  • All input values are integers.

Input

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

N

Output

Print the answer.

Sample Input 1

200

Sample Output 1

3

Three positive integers 36,100,196 satisfy the condition.

Sample Input 2

4000000000000

Sample Output 2

407073