D

在遥远的数学王国里，有三位备受尊敬的数字大师——大牛、小牛和牛魔王。他们每天都沉浸在探索数字的神秘中，乐此不疲。某一天，牛魔王提出了一个问题。

牛魔王说：“在我们王国的数字森林里，隐藏着许多神秘的数字。这些数字都有一个共同的特性：它们可以表示成某个正整数 $a$ 的 $b$ 次幂，而 $b$ 不小于 2。我想知道，在从 1 到 $N$ 的范围内，有多少这样的数字存在？”

小牛听完立马就放弃了，作为比小牛更厉害的大牛，请你帮帮牛魔王解决这个问题。

一个整数$N$， $1 \le N \le 10^{18}$

一个整数，表示满足条件的数字的个数。

输入样例 1

99

输出样例 1

12

样例 1 解释

可以写作$a^b$形式的数有1,4,8,9,16,25,27,32,36,49,64,81，一共12个。

输入样例 2

1000000000000000000

输出样例 2

1001003332

对于40%的数据，$N \le 10^6$。 对于100%的数据，$N \le 10^{18}$。