F. Взаимно простые степени
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим некоторое положительное целое число $$$x$$$. Его разложение на простые имеет вид $$$x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots$$$

Назовем число $$$x$$$ изящным, если наибольший общий делитель последовательности $$$k_1, k_2, \dots$$$ равен $$$1$$$. Например, числа $$$5 = 5^1$$$, $$$12 = 2^2 \cdot 3$$$, $$$72 = 2^3 \cdot 3^2$$$ изящные, а числа $$$8 = 2^3$$$ ($$$GCD = 3$$$), $$$2500 = 2^2 \cdot 5^4$$$ ($$$GCD = 2$$$) — нет.

Посчитайте количество изящных чисел от $$$2$$$ до $$$n$$$.

В каждом тесте содержится несколько значений $$$n$$$, для каждого из них необходимо решить задачу независимо.

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

В первой строке записано одно целое число $$$T$$$ ($$$1 \le T \le 10^5$$$) — количество значений $$$n$$$ в тесте.

В каждой из следующих $$$T$$$ строк записано одно целое число $$$n_i$$$ ($$$2 \le n_i \le 10^{18}$$$).

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

Выведите $$$T$$$ строк — в $$$i$$$-й строке должно содержаться количество изящных чисел от $$$2$$$ до $$$n_i$$$.

Пример
Входные данные
4
4
2
72
10
Выходные данные
2
1
61
6
Примечание

Приведен список не изящных чисел до $$$10$$$:

  • $$$4 = 2^2, GCD = 2$$$;
  • $$$8 = 2^3, GCD = 3$$$;
  • $$$9 = 3^2, GCD = 2$$$.

Для остальных $$$GCD = 1$$$.