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

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

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。接下来是 $t$ 个测试用例。每个测试用例的格式如下：

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 60$，对于所有 $i$)。

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

输出格式

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

样例

输入 1

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

输出 1

13
3
2305843009213693949
-1

说明 1

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