Squares and Cubes

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).

Input

The first line contains the number of test cases $t$.

Each of the next $t$ lines contains one positive integer $n(1\le n\le 10^9)$.

Output

For each test print the answer — the number of integers from $1$ to $n$ that belong to the list.

Examples