[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}$。