Олимпиадный тренинг

Задача . B. Квадраты и кубы


Поликарп очень любит квадраты и кубы положительных целых чисел. Вот начало ряда чисел, которые ему нравятся: \(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\), которые нравятся Поликарпу.


Примеры
№Входные данныеВыходные данные
1
6
10
1
25
1000000000
999999999
500000000
4
1
6
32591
32590
23125
Статистика успешных решений по компиляторам