Bessie quer dormir, mas as luzes da quinta mantêm-na acordada. Como pode apagá-las?

Bessie tem duas cadeias de bits de comprimento $N$ ($2\le N\le 20$), que representam, respetivamente, uma sequência de luzes e uma sequência de interruptores. Cada luz está acesa (1) ou apagada (0). Cada interruptor está ativo (1) ou inativo (0).

Uma jogada consiste na seguinte sequência de operações:

1. Alternar exatamente um interruptor (torná-lo ativo se estiver inativo, ou vice-versa).
2. Para cada interruptor ativo, alternar o estado da luz correspondente (apagá-la se estiver acesa, ou vice-versa).
3. Rodar ciclicamente os interruptores uma posição para a direita. Mais precisamente, se a cadeia de bits dos interruptores for inicialmente $s_0s_1\dots s_{N-1}$, passa a ser $s_{N-1}s_0s_1\dots s_{N-2}$.

Para $T$ instâncias do problema acima ($1\le T\le 2\cdot 10^5$), calcule o número mínimo de jogadas necessárias para apagar todas as luzes.

Entrada

A primeira linha contém $T$ e $N$.

Cada uma das $T$ linhas seguintes contém um par de cadeias de bits de comprimento $N$.

Saída

Para cada par, imprima o número mínimo de jogadas necessárias para apagar todas as luzes.

Exemplos

Entrada 1

4 3
000 101
101 100
110 000
111 000

Saída 1

0
1
3
2

Nota

• Primeiro caso de teste: todas as luzes já estão apagadas.
• Segundo caso de teste: alternamos o terceiro interruptor na primeira jogada.
• Terceiro caso de teste: alternamos o primeiro interruptor na primeira jogada, o segundo na segunda jogada e novamente o segundo na terceira jogada.
• Quarto caso de teste: alternamos o primeiro interruptor na primeira jogada e o terceiro na segunda jogada.

Pode demonstrar-se que, em cada caso, este é o número mínimo de jogadas necessárias.

Entrada 2

1 10
1100010000 1000011000

Saída 2

2

Nota

Pode demonstrar-se que são necessárias $2$ jogadas para apagar todas as luzes.

• Alternamos o sétimo interruptor na primeira jogada e novamente na segunda jogada.

Subtarefas

• Entradas 3-5: $N \le 8$
• Entradas 6-13: $N\le 18$
• Entradas 14-20: sem restrições adicionais.

Autores do problema: William Yue, Eric Yang e Benjamin Qi