配点 : $300$ 点

問題文

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

制約

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

入力

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

$N$

出力

答えを出力せよ。

8

6

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

100000

99634