题目描述

给定一个整数 $N$。在 $1$ 到 $N$（包括 $1$ 和 $N$）之间有多少个整数不能表示为 $a^b$ 的形式，其中 $a$ 和 $b$ 都是不小于 $2$ 的整数？

输入格式

输入$N$

输出格式

输出所求答案。

样例

8

6

100000

99634

样例1解释

4 和 8 可以表示为 $a^b$ 的形式：我们有 $2^2 = 4$ 和 $2^3 = 8$。
另一方面，1、2、3、5、6 和 7 不能用不小于 2 的整数 a 和 b 表示为 $a^b$ 的形式，所以答案是 6。

数据范围

$N$ 是一个整数
$1 \leq N \leq 10^{10}$

来源

• AtCoder ABC193C