You are given an integer K.

Consider an integer sequence $A = [A_{1}, A_{2}, \ldots, A_{N}]$.

Define another sequence S of length N, such that $S_{i} = A_{1} + A_{2} + \ldots + A_{i}$ for each 1 ≤ i ≤ N.

A is said to be interesting if A_{i} + S_{i} = K for every 1 ≤ i ≤ N.

Find the maximum length of an interesting sequence. If there are no interesting sequences, print 0.

------ Input Format ------

• The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
• Each test case consists of a single line of input, which contains a single integer K.

------ Output Format ------

• For each test case, print a new line containing one integer — the maximum length of an interesting sequence for a given value of K.

------ Constraints ------

$1 ≤ T ≤ 5000$
$1 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------
2
8
4
----- Sample Output 1 ------
3
2
----- explanation 1 ------
Test Case $1$: Consider the sequence $A = [4, 2, 1]$. $S = [4, 4 + 2, 4 + 2 + 1] = [4, 6, 7]$.
The sum of the corresponding elements of $A$ and $S$ are $4 + 4 = 8$, $2 + 6 = 8$ and $1 + 7 = 8$. Thus $A$ is an interesting sequence of size $3$.

Test Case $2$: Consider the sequence $A = [2, 1]$. $S = [2, 2 + 1] = [2, 3]$.
The sum of the corresponding elements of $A$ and $S$ are $2 + 2 = 4$ and $1 + 3 = 4$. Thus $A$ is an interesting sequence of size $2$.

It's guaranteed that, in both examples above, there doesn't exist a longer sequence satisfying the problem constraints.

见题面

见题面