注意：内存限制较为特殊。

给你一个整数 $N$ 和一个整数序列 $A = (A_1, A_2, \dots, A_N)$。

你对该序列重复进行操作，直到其长度变为 1。在每一步中，你选择当前序列中的两个相邻元素并将它们合并为一个元素。每次合并后，所得序列将按自然顺序重新编号。有以下两种操作可用：

• AND 操作：将 $A_i$ 和 $A_{i+1}$ 替换为 $(A_i \& A_{i+1})$。
• OR 操作：将 $A_i$ 和 $A_{i+1}$ 替换为 $(A_i | A_{i+1})$。

这里，运算符 $\&$ 和 $|$ 分别表示按位与（AND）和按位或（OR）操作。

由于每次操作都会使序列长度减少 1，因此总共进行恰好 $(N - 1)$ 次操作。

在所有使得最终剩下的元素等于 0 的可能操作序列中，求进行 OR 操作的最大可能次数。

输入格式

输入包含多个测试用例。

T
testcase 1
testcase 2
:
testcase T

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

N
A_1 A_2 ... A_N

数据范围

• $1 \le T \le 2^{12}$
• $2 \le N \le 2^{13}$
• $0 \le A_i < 2^{13}$
• 所有测试用例中 $N$ 的总和不超过 $2^{13}$。
• 所有输入值均为整数。

输出格式

输出在所有满足最终剩下元素等于 0 的操作序列中，可以进行 OR 操作的最大次数。如果没有操作序列满足该条件，则输出 -1。

样例

输入样例 1

4
6
3 0 1 4 1 5
2
0 1
8
2 0 1 6 1 2 0 3
10
1 7 6 7 5 7 5 3 2 7

输出样例 1

3
0
5
6

说明

该输入包含 4 个测试用例。

对于第一个测试用例，我们可以按如下方式进行 3 次第二种操作（OR 操作）：

• 初始时，$A = (3, 0, 1, 4, 1, 5)$。
• 对 $(A_3, A_4)$ 应用 OR 操作。操作后，$A = (3, 0, 5, 1, 5)$。
• 对 $(A_1, A_2)$ 应用 AND 操作。操作后，$A = (0, 5, 1, 5)$。
• 对 $(A_3, A_4)$ 应用 OR 操作。操作后，$A = (0, 5, 5)$。
• 对 $(A_2, A_3)$ 应用 OR 操作。操作后，$A = (0, 5)$。
• 对 $(A_1, A_2)$ 应用 AND 操作。操作后，$A = (0)$。

由于最终状态满足 $A_1 = 0$，因此满足条件。

无法在进行 4 次或更多次 OR 操作的情况下满足条件，因此答案为 3。