Поликарп очень любит квадраты и кубы положительных целых чисел. Вот начало ряда чисел, которые ему нравятся: \(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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач