B. Galaxy of Stars in a Dream
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Everyone has their own galaxy of stars that they long for but cannot reach.

In a dream, Xinghe has a non-negative integer $$$x$$$. He needs to find three non-negative integers $$$a, b, c$$$ such that $$$a \times b + c = x$$$. Let the maximum among these three numbers be $$$M = \max(a, b, c)$$$, and the minimum be $$$m = \min(a, b, c)$$$. His goal is to make the range $$$M - m$$$ as small as possible. Please help him determine the minimum possible value of $$$M - m$$$ among all triples $$$(a, b, c)$$$ satisfying the condition.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$), denoting the number of test cases.

For each test case, there is one line containing an integer $$$x$$$ ($$$0 \le x \le 10^{9}$$$), as described in the statement.

Output

For each test case, output one integer on a separate line, representing the minimum value of $$$M - m$$$.

Example
Input
4
1
12
1000
729320
Output
1
0
8
5