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

Bessie tiene dos cadenas de bits de longitud $N$ ($2\le N\le 20$), que representan una secuencia de luces y una secuencia de interruptores, respectivamente. Cada luz está encendida (1) o apagada (0). Cada interruptor está activo (1) o inactivo (0).

Un movimiento consiste en la siguiente secuencia de operaciones:

1. Alternar exactamente un interruptor (activarlo si está inactivo, o viceversa).
2. Para cada interruptor activo, alternar el estado de la luz correspondiente (apagarla si está encendida, o viceversa).
3. Rotar cíclicamente los interruptores una posición a la derecha. En concreto, si la cadena de bits de los interruptores es inicialmente $s_0s_1\dots s_{N-1}$, pasa a ser $s_{N-1}s_0s_1\dots s_{N-2}$.

Para $T$ instancias del problema anterior ($1\le T\le 2\cdot 10^5$), calcula el número mínimo de movimientos necesarios para apagar todas las luces.

Entrada

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

Cada una de las siguientes $T$ líneas contiene un par de cadenas de bits de longitud $N$.

Salida

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

Ejemplos

Entrada 1

4 3
000 101
101 100
110 000
111 000

Salida 1

0
1
3
2

Nota

• Primer caso de prueba: todas las luces ya están apagadas.
• Segundo caso de prueba: alternamos el tercer interruptor en el primer movimiento.
• Tercer caso de prueba: alternamos el primer interruptor en el primer movimiento, el segundo en el segundo movimiento y el segundo otra vez en el tercer movimiento.
• Cuarto caso de prueba: alternamos el primer interruptor en el primer movimiento y el tercero en el segundo movimiento.

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

Entrada 2

1 10
1100010000 1000011000

Salida 2

2

Nota

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

• Alternamos el séptimo interruptor en el primer movimiento y otra vez en el segundo movimiento.

Subtareas

• Entradas 3-5: $N \le 8$
• Entradas 6-13: $N\le 18$
• Entradas 14-20: sin restricciones adicionales.

Autores del problema: William Yue, Eric Yang y Benjamin Qi