eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Непредставимые

Непредставимые

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Задано натуральное число n. Сколько чисел от 1 до n (включительно) непредставимы в виде a^b, где a и b — натуральные числа, не менее 2?

Входные данные

Одно натуральное число n~(n \le 10^{10}).

Выходные данные

Выведите количество непредставимых чисел.

Пример

Входные данные #1
8
Выходные данные #1
6
Входные данные #2
100000
Выходные данные #2
99634