题目描述

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

输入格式

输入一个整数 $N$。

输出格式

输出所求答案。

样例 #1

样例输入 #1

8

样例输出 #1

6

样例 #2

样例输入 #2

100000

样例输出 #2

99634

输入输出样例 #1

输入 #1

8

输出 #1

6

输入输出样例 #2

输入 #2

100000

输出 #2

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 \le N \le 10^{10}$。