Квадраты и кубы

Выпишем в ряд квадраты и кубы натуральных чисел: $1,4,8,9$, ....

Для заданного значения $n$ посчитайте количество выписанных чисел от $1$ до $n$. Иными словами, найдите количество таких $x$, что $x$ является квадратом или кубом натурального числа (или и квадратом и кубом одновременно).

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

В первой строке записано количество тестов $t$.

В каждой из следующих $t$ строк записано одно натуральное число $n(1\le n\le 10^9)$.

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

Для каждого теста выведите ответ — количество чисел от $1$ до $n$, принадлежащих списку.

Примеры