E. 67-я задача про XOR
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

PMOI оказался не таким уж ужасным — поговаривали, что задачи были вполне неплохими и даже (страшно подумать) приятными! Однако, к огорчению Macaque, трое непослушных участников (Cloud, ChatGBT и Grook) начали жульничать, используя свою идеальную память на OEIS. Ну и негодяи! Внезапно Macaque пришлось срочно действовать и придумать задачу, на которой эти трое не смогли бы жульничать. Вас, пониженного из его спутника до жалкого раба, привлекли для тестирования.

Вам дан массив $$$a$$$, изначально содержащий $$$n$$$ неотрицательных целых чисел.

Вы выполняете следующую операцию ровно $$$n-1$$$ раз:

  1. Выберите индекс $$$i$$$ массива $$$a$$$ ($$$1 \leq i \leq |a|$$$, где $$$|a|$$$ обозначает текущую длину массива $$$a$$$). Пусть $$$x = a_i$$$.
  2. Присвойте $$$a_j = a_j \oplus x$$$ для всех $$$1 \leq j \leq |a|$$$, где $$$\oplus$$$ обозначает побитовую операцию XOR.
  3. Удалите $$$a_i$$$ из массива.

Можно показать, что после $$$n-1$$$ операций в массиве останется ровно один элемент. Ваша задача — определить максимально возможное значение этого последнего оставшегося элемента, если выполнять операции оптимально.

Входные данные

Каждый набор входных данных содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 100$$$). Далее следуют описания наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 3105$$$) — исходную длину массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$3105$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимально возможное значение последнего элемента.

Пример
Входные данные
3
2
67 67
3
1 2 3
10
67 667 167 867 267 467 367 567 767 967
Выходные данные
0
3
1012
Примечание

Во втором наборе входных данных массив равен $$$[1, 2, 3]$$$. Одна из оптимальных последовательностей операций выглядит так:

  1. Выберите элемент $$$3$$$. Удалите его. Оставшиеся элементы станут равны $$$[1 \oplus 3, 2 \oplus 3] = [2, 1]$$$.
  2. Выберите элемент $$$2$$$. Удалите его. Оставшийся элемент станет равен $$$[1 \oplus 2] = [3]$$$.
Итоговое значение равно $$$3$$$.