Выпишем в ряд квадраты и кубы натуральных чисел: 1,4,8,9, ....
Для заданного значения n посчитайте количество выписанных чисел от 1 до n. Иными словами, найдите количество таких x, что x является квадратом или кубом натурального числа (или и квадратом и кубом одновременно).
В первой строке записано количество тестов t.
В каждой из следующих t строк записано одно натуральное число n (1≤n≤109).
Для каждого теста выведите ответ — количество чисел от 1 до n, принадлежащих списку.