题目描述

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

输入格式

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

$N$

输出格式

答えを出力せよ。

题目大意

[ABC193C] Unexpressed

题目描述

给出一个整数 $n$，输出在 1~ $n$ 之间的所有整数中，有多少个不能被 $a^{b} \left(a \ge 2 \And b \ge 2 \right)$ 表示的数。

输入格式

输入一个整数 $n$。

输出格式

输出在 1~ $n$ 之间的所有整数中，有多少个不能被 $a^{b} \left(a \ge 2 \And b \ge 2 \right)$ 表示的数。

样例 #1

样例输入 #1

8

样例输出 #1

6

样例 #2

样例输入 #2

100000

样例输出 #2

99634

提示

制约

• $n$ 是一个整数
• $1 \le n \le 10^{10}$

样例1说明

只有 4 , 8 能被 $a^{b} \left(a \ge 2 \And b \ge 2 \right)$ 表示，$4=2^{2}$，$8=2^{3}$。

8

6

100000

99634

提示

制約

• $N$ は整数
• $1\ <\ =\ N\ <\ =\ 10^{10}$

Sample Explanation 1

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