#P1619B. Squares and Cubes

Squares and Cubes

No submission language available for this problem.

Description

Polycarp likes squares and cubes of positive integers. Here is the beginning of the sequence of numbers he likes: $1$, $4$, $8$, $9$, ....

For a given number $n$, count the number of integers from $1$ to $n$ that Polycarp likes. In other words, find the number of such $x$ that $x$ is a square of a positive integer number or a cube of a positive integer number (or both a square and a cube simultaneously).

The first line contains an integer $t$ ($1 \le t \le 20$) — the number of test cases.

Then $t$ lines contain the test cases, one per line. Each of the lines contains one integer $n$ ($1 \le n \le 10^9$).

For each test case, print the answer you are looking for — the number of integers from $1$ to $n$ that Polycarp likes.

Input

The first line contains an integer $t$ ($1 \le t \le 20$) — the number of test cases.

Then $t$ lines contain the test cases, one per line. Each of the lines contains one integer $n$ ($1 \le n \le 10^9$).

Output

For each test case, print the answer you are looking for — the number of integers from $1$ to $n$ that Polycarp likes.

Samples

6
10
1
25
1000000000
999999999
500000000
4
1
6
32591
32590
23125