Problem Statement

You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\dots,A_N)$.

You can perform the following operation on $A$ any number of times, possibly zero:

• Choose a positive integer $x_0$, and set $x=x_0$. Then, for $i=1,2,\ldots,N$ in this order, do the following:
• Subtract $x$ from $A_i$, and replace $x$ with $\displaystyle \left\lfloor \frac x2\right\rfloor$.

Determine whether it is possible to make all elements of $A$ equal to $0$, and if it is possible, find the minimum number of operations required to do so.

You are given $T$ test cases; solve each of them.

Constraints

• $1\le T\le 10^4$
• $1\le N\le 30$
• $0\le A_i\le 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
A_1 A_2 \ldots A_N

Output

Output the answers for the test cases in order, separated by newlines.

For each test case, if it is possible to make all elements of $A$ equal to $0$, output the minimum number of operations required to do so; if it is not possible, output -1.