Поликарп очень любит квадраты и кубы положительных целых чисел. Вот начало ряда чисел, которые ему нравятся: $$$1$$$, $$$4$$$, $$$8$$$, $$$9$$$, ....
Для заданного числа $$$n$$$ посчитайте количество чисел от $$$1$$$ до $$$n$$$, которые нравятся Поликарпу. Иными словами, найдите количество таких $$$x$$$, что $$$x$$$ является квадратом натурального числа или кубом натурального числа (или и квадратом и кубом одновременно).
В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 20$$$) — количество наборов входных данных в тесте.
Далее в $$$t$$$ строках записаны наборы входных данных по одному в строке. Каждая из строк содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$).
Для каждого набора входных данных выведите искомый ответ — количество чисел от $$$1$$$ до $$$n$$$, которые нравятся Поликарпу.
6 10 1 25 1000000000 999999999 500000000
4 1 6 32591 32590 23125
| Codeforces Round 762 (Div. 3) |
|---|
| Закончено |
