Unexpressed

题目描述

[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

输入输出样例 #1

输入 #1

8

输出 #1

6

输入输出样例 #2

输入 #2

100000

输出 #2

99634

说明/提示

制约

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

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