C - Unexpressed /

### 制約

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

### 入力

N


### 入力例 1

8


### 出力例 1

6


4, 82^2 = 4,\ 2^3 = 8 と、a^b の形で表すことができます。
1, 2, 3, 5, 6, 72 以上の整数 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


### 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