给你一个从 $$$0$$$ 到 $$$n-1$$$ 的整数排列 $$$p$$$(每个排列只出现一次)。最初,排列未排序(即,对于至少一个 $$$1 \le i \le n - 1$$$,$$$p_i>p_{i+1}$$$)。
如果可以通过执行以下有限次数的操作来对排列进行排序,则该排列被称为 $$$X$$$-对于某些非负整数 $$$X$$$ 可排序:
- 选择两个索引 $$$i$$$ 和 $$$j$$$ $$$(1 \le i \lt j \le n)$$$ 使得 $$$p_i \& p_j = X$$$。
- 交换 $$$p_i$$$ 和 $$$p_j$$$。
这里$$$\&$$$表示按位与运算。
找到 $$$X$$$ 的最大值,使得 $$$p$$$ 是 $$$X$$$ 可排序的。可以证明$$$X$$$ 总是存在某个值使得$$$p$$$ 是$$$X$$$ 可排序的。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — 排列的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, ..., p_n$$$ ($$$0 \le p_i \le n-1$$$,所有 $$$p_i$$$ 都是不同的)— $$$p$$$ 的元素。保证 $$$p$$$ 没有排序。
保证所有情况下 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例输出一个整数 - $$$X$$$ 的最大值,使得 $$$p$$$ 是 $$$X$$$ 可排序的。
示例
输入 #1
4 4 0 1 3 2 2 1 0 7 0 1 2 3 5 6 4 5 0 3 2 1 4
输出 #1
2 0 4 1
注意
在第一个测试用例中,唯一可进行 $$$X$$$ 排序的 $$$X$$$ 是 $$$X = 0$$$ 和 $$$X = 2$$$,其中最大值为 $$$2$$$。
使用 $$$X = 0$$$ 排序:
- 交换 $$$p_1$$$ 和 $$$p_4$$$,$$$p = [2, 1, 3, 0]$$$。
- 交换 $$$p_3$$$ 和 $$$p_4$$$,$$$p = [2, 1, 0, 3]$$$。
- 交换 $$$p_1$$$ 和 $$$p_3$$$,$$$p = [0, 1, 2, 3]$$$。
使用 $$$X = 2$$$ 排序:
- 交换 $$$p_3$$$ 和 $$$p_4$$$,$$$p = [0, 1, 2, 3]$$$。
在第二个测试用例中,我们必须交换 $$$p_1$$$ 和 $$$p_2$$$,这只有在 $$$X = 0$$$ 时才可能。