C - Unexpressed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数 N が与えられます。 1 以上 N 以下の整数のうち、 2 以上の整数 a, b を用いて a^b と表せないものはいくつあるでしょうか？

制約

  • N は整数
  • 1 ≤ N ≤ 10^{10}

入力

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

N

出力

答えを出力せよ。

入力例 1

8

出力例 1

6

4, 8 は 2^2 = 4,\ 2^3 = 8 と、a^b の形で表すことができます。
1, 2, 3, 5, 6, 7 は 2 以上の整数 a, b を用いて a^b と表せないので、答えは 6 です。

入力例 2

100000

出力例 2

99634

Score : 300 points

Problem Statement

Given is an integer N. How many integers between 1 and N (inclusive) are unrepresentable as a^b, where a and b are integers not less than 2?

Constraints

  • N is an integer.
  • 1 ≤ N ≤ 10^{10}

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

8

Sample Output 1

6

4 and 8 are representable as a^b: we have 2^2 = 4 and 2^3 = 8.
On the other hand, 1, 2, 3, 5, 6, and 7 are unrepresentable as a^b using integers a and b not less than 2, so the answer is 6.

Sample Input 2

100000

Sample Output 2

99634