#MX76. 数字大师

数字大师

题目描述

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

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

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

输入格式

一个整数NN, 1≤N≤10181 \le N \le 10^{18}

输出格式

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

样例 1 输入

99

样例 1 输出

12

样例 1 解释

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

样例 2 输入

1000000000000000000

样例 2 输出

1001003332

对于40%的数据,N≤106N \le 10^6。