B. Сортировка с И
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p$$$ целых чисел от $$$0$$$ до $$$n-1$$$ (каждое из них встречается ровно один раз). Первоначально перестановка не отсортирована (то есть, $$$p_i>p_{i+1}$$$ хотя бы для одного $$$1 \le i \le n - 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$$$-сортируемой.

Пример
Входные данные
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
Примечание

В первом наборе входных данных единственными $$$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$$$.