Description

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⁵ distance in front of the initial position. Next, there are q 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.

Input

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

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

Output

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

2
8
7

2
2

Hint

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

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