[Solution] The Ultimate Square Codeforces Solution

A. The Ultimate Square

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You have 𝑛$n$ rectangular wooden blocks, which are numbered from 1$1$ to 𝑛$n$. The 𝑖$i$-th block is 1$1$ unit high and ⌈𝑖2⌉$\lceil \frac{i}{2}\rceil$ units long.

Here, ⌈𝑥2⌉$\lceil \frac{x}{2}\rceil$ denotes the result of division of 𝑥$x$ by 2$2$, rounded up. For example, ⌈42⌉=2$\lceil \frac{4}{2}\rceil =2$ and ⌈52⌉=⌈2.5⌉=3$\lceil \frac{5}{2}\rceil =\lceil 2.5\rceil =3$.

For example, if 𝑛=5$n=5$, then the blocks have the following sizes: 1×1$1\times 1$, 1×1$1\times 1$, 1×2$1\times 2$, 1×2$1\times 2$, 1×3$1\times 3$.

The available blocks for 𝑛=5$n=5$

Find the maximum possible side length of a square you can create using these blocks, without rotating any of them. Note that you don't have to use all of the blocks.

One of the ways to create 3×3$3\times 3$ square using blocks 1$1$ through 5$5$

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$) — the number of test cases.

The first line of each test case contains a single integer 𝑛$n$ (1≤𝑛≤109$1\le n\le {10}^9$) — the number of blocks.

Output

For each test case, print one integer — the maximum possible side length of a square you can create.

Note

In the first test case, you can create a 1×1$1\times 1$ square using only one of the blocks.

In the second test case, one of the possible ways to create a 3×3$3\times 3$ square is shown in the statement. It is impossible to create a 4×4$4\times 4$ or larger square, so the answer is 3$3$.