Y los reunió en el lugar que en hebreo se llama Armagedón.

Apocalipsis 16:16

En un contexto bíblico, Armagedón (o Har-Magedón) es mencionado en el libro de Apocalipsis 16:16 como el lugar donde tendrá lugar la batalla final entre las fuerzas del bien y del mal en el fin de los tiempos.

Har-Magedón en hebreo significa "Monte de Megido" o "Colina de Megido". Megido es un lugar histórico en Israel conocido como un campo de batalla clave en varias guerras antiguas. Sin embargo, en el Apocalipsis, este lugar adquiere un significado simbólico como el escenario del enfrentamiento final entre Cristo y los ejércitos de Satanás.

Para una secuencia ~A~, una secuencia ~S~ es una subsecuencia de ~A~ si y solo si puede ser obtenida eliminando algunos elementos de ~A~ (es posible no eliminar ninguno).

La tabla de abajo muestra algunos ejemplos de subsecuencias de una secuencia ~A = [3,2,1,2]~.

Subsecuencia	Cómo puede ser obtenida desde ~A~
~[~3, 2, 1, 2~]~	No se elimina ningún elemento
~[~2, 1, 2~]~	~[~ 3 , 2, 1, 2~]~
~[~3, 2~]~	~[~3, 2, 1, 2~]~ o ~[~3, 2, 1, 2 ~]~
~[~3~]~	~[~3, 2, 1, 2 ~]~
~[~ ~]~	~[~ 3, 2, 1, 2 ~]~

Por otro lado, ~[3,3]~ o ~[1,3]~ no son subsecuencias de ~A~.

El AND bit a bit de dos enteros no negativos ~A~ y ~B~ (~A~ ~\&~ ~B~) se define de la siguiente manera:

• Cuando ~A~ ~\&~ ~B~ se escribe en base dos, el dígito en el lugar de ~2^k~ (~k \ge 0~) es ~1~ si ambos dígitos en ese lugar de ~A~ y ~B~ son ~1~, y ~0~ en caso contrario.

Por ejemplo, ~3~ ~\&~ ~5~ ~=~ ~1~ (en base dos, ~011~ ~\&~ ~101~ ~=~ ~001~).

De manera general, el ~\&~ bit a bit de ~m~ enteros no negativos ~p_1,p_2,p_3,\ldots,p_m~ se define como ~(\ldots ((~ ~p_1~ ~\&~ ~p_2)~ ~\&~ ~p_3)~ ~\&~ ~\ldots~ ~p_m)~. Se puede demostrar que este valor no depende del orden de ~p_1,p_2,p_3,\ldots,p_m~.

Los historiadores han encontrado una secuencia ~A~ y un entero no negativo ~K~. Ellos definen el AND-Magedón de ~A~ como el máximo valor de ~S_1 \,\&\, S_2 \,\&\, \ldots \,\&\, S_K~ donde ~S~ es una subsecuencia de ~A~ de tamaño ~K~. Ayuda a los historiadores a computar el AND-Magedón de la secuencia ~A~.

Entrada

La primera línea de la entrada contiene un entero ~T~ ~-~ la cantidad de casos de prueba a procesar.

A continuación se describe el formato de cada caso de prueba:

• La primera línea contiene dos enteros ~N~ y ~K~ ~-~ el tamaño de la secuencia ~A~ y el tamaño de la subsecuencia ~S~, respectivamente.
• La segunda línea contiene ~N~ enteros no negativos ~A_1, A_2, \ldots, A_N~ ~-~ los elementos de la secuencia ~A~.

Salida

La salida debe contener ~T~ líneas ~-~ el AND-Magedón de cada caso de prueba.

Restricciones

• ~1 \le T \le 100~
• ~1 \le K \le N \le 10^6~
• ~0 \le A_i \le 10^{18}~
• ~\sum N \le 10^6~

Subtareas

Subtarea	Restricciones Adicionales	Puntos	Dependencias
~1~	~K=1~	~10~	~-~
~2~	~1 \le K \le \min(N, 2)~; ~\sum N \le 10^3~	~15~	~-~
~3~	~\sum N \le 20~	~15~	~-~
~4~	~\sum N^K \leq 10^6~	~20~	~1~
~5~	~A_i=2^e~ (~0 \le e \le 59~) para cada ~i~ tal que ~1 \le i \le N~	~10~	~-~
~6~	~-~	~30~	~1-5~

Ejemplos

Entrada 1

1
10 1
3 1 4 1 5 9 2 6 5 3

Salida 1

9

Entrada 2

1
5 3
13 14 0 28 31

Salida 2

12

Entrada 3

1
3 2
256 4 65536

Salida 3

0