Bessie quiere dormir, pero las luces de la granja la tienen despiert. ¿Cómo puede apagarlas?

Bessie tiene dos cadenas de bits de longitud ~N~, representando una sucesión de luces y una sucesión de interruptores, respectivamente. Cada luz está o prendida (1) o apagada (0). Cada interruptor está o activo (1) o inactivo (0).

Un movimiento consiste de la siguiente secuencia de operaciones:

1. Cambiar exactamente un interruptor (ponerlo activo si está inactivo, o viceversa).
2. Para cada interruptor activo, cambie el estado de la luz correspondiente (apaguela si está prendida, o viceversa).
3. Rotar ciclicamente los interruptores a la derecha por uno. Especificamente, si la cadena de bits correspondiente a los interruptores es inicialmente ~s_0s_1...s_{N-1}~ entonces se vuelve ~s_{N-1}s_0s_1...s_{N-2}~.

Para ~T~ instancias del problema descrito, cuente el mínimo número de movimientos requeridos para apagar todas las luces.

Entrada

La primera línea contiene ~T~ y ~N~.

Cada una de las ~T~ líneas siguientes contiene un para de cadenta de bits de longitud ~N~.

Salida

Para cada par, el número mínimo de movimientos requeridos para apagar todas las luces.

Restricciones

• ~2 \leq N \leq 20~
• ~1 \leq T \leq 2 \cdot 10^5~

Ejemplo #1 de Entrada

4 3
000 101
101 100
110 000
111 000

Ejemplo #1 de Salida

0
1
3
2

• Primer caso de prueba: las luces están ya todas apagadas.
• Segundo caso de prueba: Cambiamos el tercer interruptor en el primer movimiento.
• Tercer caso de prueba: cambiamos el primer interruptor en el primer movimiento, el segundo interruptor en el segundo movimiento, y el segundo interruptro nuevamente en el tercer movimiento.
• Cuarto caso de prueba: cambiamos el primer interruptor en el primer movmiento y el tercer interruptor en el segundo movimiento.

Se puede demostrar que en cada caso este el número mínimo de movimientos necesarios.

Ejemplo #2 de Entrada

1 10
1100010000 1000011000

Ejemplo #2 de Salida

2

Se puede demostrar que 2 movimientos se necesitan para apagar todas la luces.

• Volteamos el séptimo interruptor en el primer movimiento y luego nuevamente en el segundo movimiento.

USACO 2023 January Contest, Gold Problem 2. Lights Off.