Bessie veut dormir, mais les lumières de la ferme la tiennent éveillée. Comment peut-elle les éteindre ?

Bessie possède deux chaînes de bits de longueur $N$ ($2\le N\le 20$), représentant respectivement une suite de lumières et une suite d'interrupteurs. Chaque lumière est allumée (1) ou éteinte (0). Chaque interrupteur est actif (1) ou inactif (0).

Un coup consiste en la séquence d'opérations suivante :

1. Basculer exactement un interrupteur (le rendre actif s'il est inactif, et inversement).
2. Pour chaque interrupteur actif, basculer l'état de la lumière correspondante (l'éteindre si elle est allumée, et inversement).
3. Effectuer une rotation cyclique des interrupteurs d'une position vers la droite. Plus précisément, si leur chaîne de bits est initialement $s_0s_1\dots s_{N-1}$, elle devient $s_{N-1}s_0s_1\dots s_{N-2}$.

Pour $T$ instances du problème ci-dessus ($1\le T\le 2\cdot 10^5$), calculez le nombre minimal de coups nécessaires pour éteindre toutes les lumières.

Entrée

La première ligne contient $T$ et $N$.

Chacune des $T$ lignes suivantes contient une paire de chaînes de bits de longueur $N$.

Sortie

Pour chaque paire, affichez le nombre minimal de coups nécessaires pour éteindre toutes les lumières.

Exemples

Entrée 1

4 3
000 101
101 100
110 000
111 000

Sortie 1

0
1
3
2

Remarque

• Premier test : toutes les lumières sont déjà éteintes.
• Deuxième test : nous basculons le troisième interrupteur au premier coup.
• Troisième test : nous basculons le premier interrupteur au premier coup, le deuxième au deuxième coup, puis de nouveau le deuxième au troisième coup.
• Quatrième test : nous basculons le premier interrupteur au premier coup et le troisième au deuxième coup.

On peut montrer que, dans chaque cas, il s'agit du nombre minimal de coups nécessaires.

Entrée 2

1 10
1100010000 1000011000

Sortie 2

2

Remarque

On peut montrer que $2$ coups sont nécessaires pour éteindre toutes les lumières.

• Nous basculons le septième interrupteur au premier coup, puis de nouveau au deuxième coup.

Sous-tâches

• Entrées 3-5 : $N \le 8$
• Entrées 6-13 : $N\le 18$
• Entrées 14-20 : aucune contrainte supplémentaire.

Auteurs du problème : William Yue, Eric Yang et Benjamin Qi