Although Jerry is a mouse, he likes perfect square numbers. If a number can be expressed as the square of an integer, it is called perfect square numbers. Jerry can use magic to move forward or backward a distance of any perfect square numbers, which costs a grain of rice each time. And the position after each use of magic can not be behind the initial position or more than 10^5 distance in front of the initial position. Next, there are qq questions, each time asking how much rice at least it takes for Jerry to move forward d_i. Note that each question is an independent one.

The first line contains an integer q(1 \leq q \leq 100000), which represents the number of questions you need to solve.

Each of the next q lines contains an integer d_i(1 \leq d_i \leq 100000), which represents the distance Jerry want to move forward.

For each query, print an integer to represent the minimum cost of rice.

In the first query: 0 -> 4 -> 8.

In the second query: 0 -> 16 -> 7.