AT_arc229_b.Halving Subtraction

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.

给你一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots,A_N)$。

你可以对 $A$ 执行以下操作任意多次（包括零次）：

• 选择一个正整数 $x_0$，并令 $x=x_0$。然后，按 $i=1,2,\ldots,N$ 的顺序依次执行以下步骤：
  • 从 $A_i$ 中减去 $x$，并将 $x$ 更新为 $\displaystyle \left\lfloor \frac x2\right\rfloor$。

判断是否可能将 $A$ 的所有元素都变为 $0$；若可能，求出实现该目标所需的最少操作次数。

你将得到 $T$ 组测试数据，请分别求解每组数据。

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$

输入从标准输入中按以下格式给出：

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

每个测试用例按以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

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.

按顺序输出各测试用例的答案，答案之间用换行符分隔。

对于每个测试用例，如果可以将数组 $A$ 的所有元素都变为 $0$，则输出实现该目标所需的最少操作次数；否则输出 -1。

Sample 1 Explanation:
Consider the first test case.

By performing the operations as follows, you can make all elements of $A$ equal to $0$ in two operations:

• Choose $x_0=3$. $A=(10,4)$ becomes $A=(7,3)$.
• Choose $x_0=7$. $A=(7,3)$ becomes $A=(0,0)$.

It is impossible to make all elements of $A$ equal to $0$ in fewer than two operations, so output $2$ on the first line.

Constraints

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

样例 1 解释：
考虑第一个测试用例。

通过如下操作，可在两次操作内使数组 $A$ 的所有元素均变为 $0$：

• 选择 $x_0=3$，则 $A=(10,4)$ 变为 $A=(7,3)$；
• 选择 $x_0=7$，则 $A=(7,3)$ 变为 $A=(0,0)$。

无法在少于两次操作内使 $A$ 的所有元素变为 $0$，因此第一行输出 $2$。

限制条件

• $1\le T\le 10^4$
• $1\le N\le 30$
• $0\le A_i\le 10^9$
• 所有输入值均为整数。