Problem E
It's Hip to Be Square

Suppose we have a certain number of red square tiles, all of size $1 \times 1,$ that we would like to place, without overlapping, to form the largest two-dimensional square possible, such that the only gap is a single $1 \times 1$ square left empty in the middle. Depending on the initial number of tiles, it may not always be possible to use all the tiles to build such a configuration, i.e., some tiles may be left over.

Figure 1: Attempts to solve problem when starting with $4,$ $8,$ $12,$ and $24$ red tiles

Consider the following examples illustrated in Figure 1 (from left to right):

• Starting with only $4$ red tiles, we can form a $2 \times 2$ square, but without an empty $1 \times 1$ square in the middle. Thus there are not enough tiles to form any square with an empty $1 \times 1$ square in the middle.

• Starting with $8$ red tiles, the largest square that can be formed with an empty $1 \times 1$ square in the middle is of size $3 \times 3,$ using all $8~ \textrm{red}$ tiles. In this case, there is one layer of red tiles surrounding the empty central square.

• Starting with $12$ red tiles, we could form a $4 \times 4$ square using all the tiles, but there would be four empty $1 \times 1$ squares in the middle, i.e., an empty $2 \times 2$ square. Thus, the largest square that can be formed with an empty $1 \times 1$ square in the middle is still of size $3 \times 3,$ using only $8$ of the $12$ red tiles, and still with one layer of red tiles surrounding the empty central square (and $4$ tiles left over).

• Starting with $24$ red tiles, the largest square that can be formed with an empty $1 \times 1$ square in the middle is of size $5 \times 5,$ using all $24$ red tiles. In this case, there are two layers of red tiles surrounding the empty central square.

Given a number, $N,$ of red tiles, determine the maximum number of layers that can be used to form a square with one empty $1 \times 1$ square in the middle.

Note: This problem was inspired by a post to the LinkedIn group The Math Connection by Doddy Kastanya.

Input

The first line of input contains an integer, $T,$ the number of test cases $(1 \leq T \leq 1\, 000).$ This is followed by $T$ lines, each of which contains an integer, $N$ $(1 \leq N \leq 10^9),$ representing a number of red tiles.

Output

For each test case, $N,$ output a line containing a single integer, the maximum number of layers of red tiles that can be used to build a square with a single empty $1 \times 1$ square in the middle when starting with $N$ tiles.

5
10
24
50
200
1000000

1
2
3
6
499