Let's write out in a row the squares and cubes of positive integers: 1,4,8,9, ....
For the given value of n, count the number of written numbers from 1 to n. In other words, find the number of such x that x is a square or a cube of a positive integer (or both a square and a cube simultaneously).
The first line contains the number of test cases t.
Each of the next t lines contains one positive integer n (1≤n≤109).
For each test print the answer — the number of integers from 1 to n that belong to the list.