题目描述

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

约束条件

• $N$ 是一个整数。
• $1 ≤ N ≤ 10^{10}$

输入

从标准输入读入数据，输入格式如下：

$N$

输出

输出结果。

示例输入 1

8

示例输出 1

6

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

示例输入 2

100000

示例输出 2

99634