F - x = a^b Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

1 以上 N 以下の正整数 x であって、ある正整数 a と 2 以上の 正整数 b を用いて x=a^b と表現できるものはいくつありますか？

制約

  • 入力は全て整数
  • 1 \le N \le 10^{18}

入力

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

N

出力

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

入力例 1

99

出力例 1

12

問題文中の条件を満たす整数は 1,4,8,9,16,25,27,32,36,49,64,81 の 12 個です。

入力例 2

1000000000000000000

出力例 2

1001003332

Score : 500 points

Problem Statement

How many integers x between 1 and N, inclusive, can be expressed as x = a^b using some positive integer a and a positive integer b not less than 2?

Constraints

  • All input values are integers.
  • 1 \le N \le 10^{18}

Input

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

N

Output

Print the answer as an integer.

Sample Input 1

99

Sample Output 1

12

The integers that satisfy the conditions in the problem statement are 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81: there are 12.

Sample Input 2

1000000000000000000

Sample Output 2

1001003332