La escuela de Little Square está organizando el partido de fútbol anual. Los dos capitanes del equipo son Little Square y Little Triangle. Seleccionarán sus equipos de las ~N~ clases de la escuela. La selección del equipo funciona de la siguiente manera:

• Little Square y Little Triangle alternan eligiendo personas por turnos. Little Square va primero.

• A su vez, solo se pueden elegir estudiantes de una sola clase.

• En un turno, se puede elegir al menos uno y como máximo ~K~ estudiantes.

• En un turno, se deben seleccionar como máximo una cantidad de estudiantes igual a la cantidad de estudiantes que fueron seleccionados en el turno anterior.

• El capitán que seleccione al último alumno (s) recibe el premio Football.

A los capitanes no les importa cuántos estudiantes seleccionan en general, y todos los estudiantes son idénticos cuando se trata de habilidad futbolística. Solo les importa el premio Football. Asumiendo que ambos seleccionan óptimamente, quien lo gana?

Entrada

Cada archivo de prueba contendrá varios casos de prueba, que describen diferentes escenarios.

En la primera línea se le da ~T~, el número de casos de prueba. Siguen sus descripciones.

En la primera línea de un caso de prueba encontrará ~N~ y ~K~.

En la segunda línea de un caso de prueba, encontrará ~N~ números enteros positivos, que representan los tamaños de las clases en la escuela de Little Square.

Salida

Imprima las respuestas para los ~T~ casos de prueba, cada uno en la misma línea, sin separar por espacios. Si Little Square gana el premio en un caso de prueba, imprima ~1~; imprma ~0~ en caso contrario.

Restricciones

• ~T \le 100.000~

• Sea ~\sum{N}~ la suma de los valores de ~N~ para todos los casos de prueba en un archivo de prueba. Entonces ~\sum{N} \le 100.000~.

• ~K~, tamaño de cualquier clase ~\le 1.000.000.000~.

Subtareas

Subtarea 1 (puntos: 5)

• ~K = 1~

Subtarea 2 (puntos: 13)

• ~N \le 10~

• ~\sum{N} \le 100~

• tamaño de cualquier clase ~\le 3~.

Subtarea 3 (puntos: 12)

• ~N \le 10~

• tamaño de cualquier clase ~\le 5~.

Subtarea 4 (puntos: 10)

• ~N = 1~

• ~K~, tamaño de cualquier clase ~\le 100~.

Subtarea 5 (puntos: 10)

• ~N = 1~

Subtarea 6 (puntos: 20)

• ~K = 2~

Subtarea 7 (puntos: 15)

• ~K~ es una potencia de ~2~

Subtarea 8 (puntos: 15)

• Sin restricciones adicionales

Ejemplos

Ejemplo de entrada

3
3 1
3 1 1
5 2
2 1 1 1 1
1 2
3

Ejemplo de salida

111

Explicación

En la primera prueba, hay 5 estudiantes en total, y se debe seleccionar exactamente un estudiante en cada turno (como K = 1). Por lo tanto, la selección durará exactamente 5 turnos, y el último estudiante será seleccionado por Little Square gire, y Little Square gana.

En la segunda prueba, Little Square puede seleccionar primero a dos estudiantes de la primera clase. Luego, después de cuatro turnos más en los que cada capitán selecciona un estudiante (ya que todas las clases tienen un solo estudiante en este momento), Little Square gana.

En la tercera prueba, una estrategia ganadora tiene a Little Square primero seleccionando a un estudiante.