题目描述

给定一个从 $0$ 到 $n-1$ 的排列 $p$（每个数字恰好出现一次）。初始时，该排列未排序（即至少存在一个 $1 \le i \le n-1$ 使得 $p_i > p_{i+1}$）。

对于某个非负整数 $X$，如果可以通过以下操作若干次将排列 $p$ 排序，则称排列 $p$ 是 $X$-可排序的：

• 选择两个下标 $i$ 和 $j$（$1 \le i < 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, \ldots, p_n$（$0 \le p_i \le n-1$，所有 $p_i$ 互不相同），表示排列 $p$。保证 $p$ 未排序。

保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示最大的 $X$，使得排列 $p$ 是 $X$-可排序的。

说明/提示

在第一个测试用例中，排列 $p$ 只有在 $X=0$ 和 $X=2$ 时是 $X$-可排序的，最大值为 $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$ 时才可能。

由 ChatGPT 4.1 翻译

样例

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

2
0
4
1