A. НИТ делает orz
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы развлечь своих поклонников, гражданин НИТ решил дать им задачу, связанную с $$$\operatorname{or} z$$$. А вы сможете её решить?

Дан массив $$$a$$$ в 1-индексации, состоящий из $$$n$$$ целых чисел, а также целое число $$$z$$$. Вы можете проделать следующую операцию любое количество (возможно, ноль) раз:

  • Выбрать целое $$$i$$$, такое что $$$1\le i\le n$$$. Затем одновременно присвоить $$$a_i$$$ значение $$$(a_i\operatorname{or} z)$$$ и присвоить $$$z$$$ значение $$$(a_i\operatorname{and} z)$$$. Другими словами, если $$$x$$$ и $$$y$$$ — текущие значения $$$a_i$$$ и $$$z$$$ соответственно, то нужно положить $$$a_i$$$ равным $$$(x\operatorname{or}y)$$$, а $$$z$$$ положить равным $$$(x\operatorname{and}y)$$$.

Здесь $$$\operatorname{or}$$$ и $$$\operatorname{and}$$$ обозначают операции побитового ИЛИ и побитового И соответственно.

Найдите максимально возможное значение максимального элемента в $$$a$$$ после некоторого (возможно, нулевого) количества операций.

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

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

Первая строка набора входных данных содержит два целых числа: $$$n$$$ и $$$z$$$ ($$$1\le n\le 2000$$$, $$$0\le z<2^{30}$$$).

Вторая строка набора входных данных содержит $$$n$$$ целых чисел: $$$a_1$$$,$$$a_2$$$,$$$\ldots$$$,$$$a_n$$$ ($$$0\le a_i<2^{30}$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

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

Для каждого набора входных данных выведите одно число — ответ на задачу.

Пример
Входные данные
5
2 3
3 4
5 5
0 2 4 6 8
1 9
10
5 7
7 15 30 29 27
3 39548743
10293834 10284344 13635445
Выходные данные
7
13
11
31
48234367
Примечание

В первом наборе входных данных одной из оптимальных последовательностей действий является следующая:

  • Выполнить операцию для $$$i=1$$$. Теперь $$$a_1$$$ становится равным $$$(3\operatorname{or}3)=3$$$, а $$$z$$$ становится равным $$$(3\operatorname{and}3)=3$$$.
  • Выполнить операцию для $$$i=2$$$. Теперь $$$a_2$$$ становится равным $$$(4\operatorname{or}3)=7$$$, а $$$z$$$ становится равным $$$(4\operatorname{and}3)=0$$$.
  • Выполнить операцию для $$$i=1$$$. Теперь $$$a_1$$$ становится равным $$$(3\operatorname{or}0)=3$$$, а $$$z$$$ становится равным $$$(3\operatorname{and}0)=0$$$.

После этих операций последовательность $$$a$$$ становится равной $$$[3,7]$$$, и максимальное значение в ней равно $$$7$$$. Можно доказать, что максимальное значение в $$$a$$$ не может превосходить $$$7$$$ ни при какой последовательности операций, так что ответ равен $$$7$$$.

В четвёртом наборе входных данных одной из оптимальных последовательностей действий является следующая:

  • Выполнить операцию для $$$i=1$$$. Теперь $$$a_1$$$ становится равным $$$(7\operatorname{or}7)=7$$$, а $$$z$$$ становится равным $$$(7\operatorname{and}7)=7$$$.
  • Выполнить операцию для $$$i=3$$$. Теперь $$$a_3$$$ становится равным $$$(30\operatorname{or}7)=31$$$, а $$$z$$$ становится равным $$$(30\operatorname{and}7)=6$$$.
  • Выполнить операцию для $$$i=5$$$. Теперь $$$a_5$$$ становится равным $$$(27\operatorname{or}6)=31$$$, а $$$z$$$ становится равным $$$(27\operatorname{and}6)=2$$$.