幂表示的个数

题目描述

给定整数 $N$。在 $1$ 以上 $N$ 以下的整数中,不能用 $2$ 以上的整数 $a, b$ 表示为 $a^b$ 的有多少个呢?

输入格式

输入按以下格式从标准输入给出:

$N$

输出格式

输出答案。

样例

8

6

$4, 8$ 可以表示为 $2^2 = 4,\ 2^3 = 8$ 这种 $a^b$ 的形式。

$1, 2, 3, 5, 6, 7$ 不能用 $2$ 以上的整数 $a, b$ 表示为 $a^b$,所以答案是 $6$。

100000

99634

数据范围

• $N$ 是整数
• $1 \le N \le 10^{10}$