x = a^b

题目描述

有多少个整数 $x$ 满足 $1 \le x \le N$,且可以用某个正整数 $a$ 和不小于 $2$ 的正整数 $b$ 表示为 $x = a^b$?

输入格式

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

$N$

输出格式

以整数输出答案。

样例

99

12

满足题目条件的整数为 $1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81$,共 $12$ 个。

1000000000000000000

1001003332

数据范围

• 所有输入值均为整数。
• $1 \le N \le 10^{18}$