Дано ціле число \(N\).

Скільки цілих чисел від 1 до \(N\) (включно) не можна представити як \(a^b\), де \(a\) і \(b\) цілі числа не менші 2?

Формат вхідних даних

Вхідний потік містить ціле число \(N\) (\(1 \le N \le 10^{10}\))

Формат вихідних даних

У вихідний потік виведіть шукану кількість.

Примітка

До прикладу 1:

4 і 8 представлені як \(a^b\) : маємо \(2^2\) = 4 і \(2^3\) = 8.

Числа 1, 2, 3, 5, 6 і 7 не можна представити як \(a^b\) використовуючи цілі числа \(a\) і \(b\) не менші 2, тому відповідь 6.

Приклад вхідних даних

8

Приклад вихідних даних

6

Приклад вхідних даних

100000

Приклад вихідних даних

99634