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

Марсианские ученые исследуют Ганимед, один из многочисленных спутников Юпитера. Недавно на нем были обнаружены руины древней цивилизации. Ученые доставили на Марс несколько табличек с надписями на неизвестном науке языке.

Было установлено, что жители Ганимеда использовали алфавит из двух букв, причем каждое слово имело фиксированную длину — ровно $$$\ell$$$ букв. Поэтому ученые решили записывать каждое слово этого языка как целое положительное число от $$$0$$$ до $$$2^{\ell} - 1$$$. Первой букве алфавита соответствуют нули в двоичной записи числа, а второй букве алфавита — единицы.

Одно и то же слово может иметь в языке разные формы. Тогда необходимо восстановить начальную форму слова. Ниже описано, как это делается.

Назовем расстоянием между двумя словами количество позиций, в которых эти слова различаются. Например, расстояние между словами $$$1001_2$$$ и $$$1100_2$$$ (в двоичной записи) равно двум, т. к. они имеют разные буквы на второй и четвертой позициях, если считать слева направо. Будем в дальнейшем обозначать расстояние между словами $$$x$$$ и $$$y$$$ как $$$d(x, y)$$$.

Пусть слово имеет $$$n$$$ форм, $$$i$$$-я из которых описывается целым числом $$$x_i$$$. Все $$$x_i$$$ не обязательно различны, т. к. две разные формы слова могут записываться одинаково. Рассмотрим некоторое слово $$$y$$$. Тогда близость слова $$$y$$$ равна сумме расстояний до каждой из форм исследуемого слова, т. е. сумме $$$d(x_i, y)$$$ по всем $$$1 \le i \le n$$$.

Начальной формой является слово $$$y$$$ с минимально возможной близостью.

Вам необходимо помочь ученым и написать программу, которая находит начальную форму слова по всем его известным формам. Обратите внимание, что начальная форма не обязательно должна совпадать с какой-либо из известных $$$n$$$ форм слова.

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

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

В первой строке каждого набора входных данных находится два целых числа $$$n$$$ и $$$\ell$$$ ($$$1 \le n \le 100$$$, $$$1 \le \ell \le 30$$$) — количество форм слова и количество букв в одной форме.

Во второй строке каждого набора входных данных находится $$$n$$$ целых чисел $$$x_i$$$ ($$$0 \le x_i \le 2^\ell - 1$$$) — формы слова. Числа не обязательно являются различными.

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

Для каждого теста выведите одно целое число — начальную форму слова, т. е. такое $$$y$$$ ($$$0 \le y \le 2^\ell - 1$$$), что сумма $$$d(x_i, y)$$$ по всем $$$1 \le i \le n$$$ минимально возможная. Обратите внимание, что $$$y$$$ не обязано совпадать с каким-либо числом из $$$x_i$$$.

Если вариантов восстановить начальную форму слова несколько, выведите любой из них.

Пример
Входные данные
7
3 5
18 9 21
3 5
18 18 18
1 1
1
5 30
1 2 3 4 5
6 10
99 35 85 46 78 55
2 1
0 1
8 8
5 16 42 15 83 65 78 42
Выходные данные
17
18
1
1
39
0
2
Примечание

Рассмотрим примеры из условия.

В первом примере слова в двоичной записи записываются как $$$x_1 = 10010_2$$$, $$$x_2 = 01001_2$$$ и $$$x_3 = 10101_2$$$. Пусть $$$y = 10001_2$$$. Тогда $$$d(x_1, y) = 2$$$ (различие в четвертой и пятой позиции), $$$d(x_2, y) = 2$$$ (различие в первой и второй позиции), $$$d(x_3, y) = 1$$$ (различие в третьей позиции). Получаем, что близость равна $$$2 + 2 + 1 = 5$$$. Можно показать, что меньшего значения близости добиться невозможно.

Во втором примере все формы слова одинаковы и равны $$$18$$$ ($$$10010_2$$$ в двоичной записи), поэтому начальная форма тоже равна $$$18$$$. Как нетрудно догадаться, близость в таком случае равна нулю.