eolymp
bolt
Try our new interface for solving problems
Problems

Squares and Cubes

Squares and Cubes

Time limit 1 second
Memory limit 128 MiB

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 data

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 data

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

Examples

Input example #1
5
1
10
25
1000000
987654321
Output example #1
1
4
6
1090
32390