题目描述

对于一个非负整数 $x$，令 $p(x)$ 为 $x$ 的二进制表示中 1 的个数。例如，$p(26)=3$，因为 $26=(11010)_2$。

给定一个包含 $n$ 个整数的序列 $(a_1, a_2, ..., a_n)$。你的任务是判断是否存在一个非负整数 $x$，使得序列 $(p(x), p(x+1), ..., p(x+n-1))$ 与 $(a_1, a_2, ..., a_n)$ 相等。此外，如果存在，你需要计算满足条件的最小的 $x$。

输入格式

输入的第一行包含一个整数 $t (1 \le t \le 1000)$，代表测试用例的数量。之后是 $t$ 个测试用例。每个测试用例的格式如下。

第一行包含一个整数 $n (1 \le n \le 500,000)$。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n(0 \le a_i \le 60)$。

在单个输入文件中，所有测试用例的 $n$ 的总和不超过 $500,000$。

输出格式

对于每个测试用例，输出满足上述条件的最小非负整数 $x$。如果不存在这样的 $x$，则输出 $-1$。

4
5
3 3 4 1 2
3
2 1 2
2
60 60
2
8 0

13
3
2305843009213693949
-1

提示

样例解释 #1

对于第一个测试用例，$x=13$ 满足上述条件，因为 $(p(13), p(14), p(15), p(16), p(17))=(3, 3, 4, 1, 2)$。可以证明，不存在比 $13$ 更小的非负整数满足上述条件。

翻译由 Gemini 2.5 Pro 完成。