103615: [Atcoder]ABC361 F - x = a^b

Problem Statement

How many integers $x$ between $1$ and $N$, inclusive, can be expressed as $x = a^b$ using some positive integer $a$ and a positive integer $b$ not less than $2$?

Constraints

• All input values are integers.
• $1 \le N \le 10^{18}$

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the answer as an integer.

Sample Input 1

99

Sample Output 1

12

The integers that satisfy the conditions in the problem statement are $1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81$: there are $12$.

Sample Input 2

1000000000000000000

Sample Output 2

1001003332

问题陈述

在1和N之间（包括1和N），有多少个整数x可以用某个正整数a和一个不低于2的正整数b表示为x = a^b?

约束条件

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

输入

输入从标准输入以以下格式给出：

$N$

输出

以整数形式打印答案。

示例输入1

99

示例输出1

12

满足问题陈述中条件的整数有$1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81$：共有12个。

示例输入2

1000000000000000000

示例输出2

1001003332