A. Абсолютная максимизация
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$. Вы можете применить следующую операцию несколько (возможно, ноль) раз:

  • Выбрать $$$i$$$, $$$j$$$, $$$b$$$: Поменять местами $$$b$$$-й бит в бинарной записи $$$a_i$$$ и $$$a_j$$$.

В бинарной записи биты нумеруются справа (наименее значимый) налево (наиболее значимый). Учтите, что в начале любой бинарной записи имеется бесконечное число начальных нулевых битов.

Например, поменять местами $$$0$$$-й бит для $$$4=100_2$$$ и $$$3=11_2$$$ даст в результате $$$101_2=5$$$ и $$$10_2=2$$$. Поменять местами $$$2$$$-й бит для $$$4=100_2$$$ и $$$3=11_2$$$ даст в результате $$$000_2=0_2=0$$$ и $$$111_2=7$$$.

Найдите максимальное значение $$$\max(a) - \min(a)$$$.

Тут $$$\max(a)$$$ означает максимальный элемент $$$a$$$ и $$$\min(a)$$$ означает минимальный элемент $$$a$$$.

Бинарная запись $$$x$$$ — это $$$x$$$ записанное в системе счисления с основанием $$$2$$$. Например, $$$9$$$ и $$$6$$$ записанные в системе счисления с основанием $$$2$$$ это $$$1001$$$ и $$$110$$$, соответственно.

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

В первой строке содержится одно целое число $$$t$$$ ($$$1 \le t \le 128$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$3 \le n \le 512$$$) — длину массива $$$a$$$.

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

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

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

Для каждого набора входных данных выведите одно целое число — максимальное возможное значение $$$\max(a) - \min(a)$$$.

Пример
Входные данные
4
3
1 0 1
4
5 5 5 5
5
1 2 3 4 5
7
20 85 100 41 76 49 36
Выходные данные
1
0
7
125
Примечание

В первом примере может быть показано, что не надо делать никаких операций — максимальное значение $$$\max(a) - \min(a)$$$ это $$$1 - 0 = 1$$$.

Во втором примере ни одна операция не может изменить массив — максимальное значение $$$\max(a) - \min(a)$$$ это $$$5 - 5 = 0$$$.

В третьем примере изначально $$$a = [1, 2, 3, 4, 5]$$$, мы можем применить операцию $$$i = 2$$$, $$$j = 5$$$, $$$b = 1$$$. Массив станет равен $$$a = [1, 0, 3, 4, 7]$$$. Может быть показано, что последующие операции не приведут к улучшению ответ. Таким образом, максимальное значение это $$$\max(a) - \min(a) = 7 - 0 = 7$$$.