问题描述

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

约束条件

• $N$是一个整数。
• $1 \leq N \leq 10^{10}$

输入

输入通过标准输入给出，格式如下：

N

输出

打印答案。

样例输入1

8

样例输出1

6

$4$和$8$可以表示为$a^b$：我们有$2^2 = 4$和$2^3 = 8$。另一方面，$1$、$2$、$3$、$5$、$6$和$7$不能使用不小于$2$的整数$a$和$b$表示为$a^b$的形式，因此答案是$6$。

样例输入2

100000

样例输出2

99634