#P1682B. AND Sorting

AND Sorting

Description

You are given a permutation pp of integers from 00 to n1n-1 (each of them occurs exactly once). Initially, the permutation is not sorted (that is, pi>pi+1p_i>p_{i+1} for at least one 1in11 \le i \le n - 1).

The permutation is called XX-sortable for some non-negative integer XX if it is possible to sort the permutation by performing the operation below some finite number of times:

  • Choose two indices ii and jj (1i<jn)(1 \le i \lt j \le n) such that pi&pj=Xp_i \& p_j = X.
  • Swap pip_i and pjp_j.

Here &\& denotes the bitwise AND operation.

Find the maximum value of XX such that pp is XX-sortable. It can be shown that there always exists some value of XX such that pp is XX-sortable.

题面翻译

TT 次询问。每次询问给你一个 0n10 \sim n - 1 的排列 p1,p2,,pnp_1, p_2, \ldots, p_n,保证此排列初始时没有排好序。你可以初始指定一个数 XX,然后你每次可以交换两个数 pi,pjp_i, p_j,此时必须满足 pi&pj=Xp_i \mathbin{\&} p_j = X,问要使得原排列有序的 XX 的最大值。

Input

The input consists of multiple test cases. The first line contains a single integer tt (1t104)(1 \le t \le 10^4)  — the number of test cases. Description of test cases follows.

The first line of each test case contains a single integer nn (2n2105)(2 \le n \le 2 \cdot 10^5)  — the length of the permutation.

The second line of each test case contains nn integers p1,p2,...,pnp_1, p_2, ..., p_n (0pin10 \le p_i \le n-1, all pip_i are distinct)  — the elements of pp. It is guaranteed that pp is not sorted.

It is guaranteed that the sum of nn over all cases does not exceed 21052 \cdot 10^5.

Output

For each test case output a single integer — the maximum value of XX such that pp is XX-sortable.

输入数据 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

Note

In the first test case, the only XX for which the permutation is XX-sortable are X=0X = 0 and X=2X = 2, maximum of which is 22.

Sorting using X=0X = 0:

  • Swap p1p_1 and p4p_4, p=[2,1,3,0]p = [2, 1, 3, 0].
  • Swap p3p_3 and p4p_4, p=[2,1,0,3]p = [2, 1, 0, 3].
  • Swap p1p_1 and p3p_3, p=[0,1,2,3]p = [0, 1, 2, 3].

Sorting using X=2X = 2:

  • Swap p3p_3 and p4p_4, p=[0,1,2,3]p = [0, 1, 2, 3].

In the second test case, we must swap p1p_1 and p2p_2 which is possible only with X=0X = 0.