Bessie möchte schlafen gehen, aber die Lichter auf der Farm halten sie wach. Wie kann sie sie ausschalten?

Bessie hat zwei Bitfolgen der Länge $N$ ($2\le N\le 20$), die eine Folge von Lichtern beziehungsweise eine Folge von Schaltern darstellen. Jedes Licht ist entweder an (1) oder aus (0). Jeder Schalter ist entweder aktiv (1) oder inaktiv (0).

Ein Zug besteht aus der folgenden Abfolge von Operationen:

1. Genau einen Schalter umschalten (ihn aktivieren, wenn er inaktiv ist, oder umgekehrt).
2. Für jeden aktiven Schalter den Zustand des zugehörigen Lichts umschalten (es ausschalten, wenn es an ist, oder umgekehrt).
3. Die Schalter zyklisch um eine Position nach rechts verschieben. Wenn die Bitfolge der Schalter anfangs $s_0s_1\dots s_{N-1}$ ist, wird sie also zu $s_{N-1}s_0s_1\dots s_{N-2}$.

Bestimme für $T$ Instanzen des obigen Problems ($1\le T\le 2\cdot 10^5$) die minimale Anzahl von Zügen, um alle Lichter auszuschalten.

Eingabe

Die erste Zeile enthält $T$ und $N$.

Die nächsten $T$ Zeilen enthalten jeweils ein Paar von Bitfolgen der Länge $N$.

Ausgabe

Gib für jedes Paar die minimale Anzahl von Zügen aus, um alle Lichter auszuschalten.

Beispiele

Eingabe 1

4 3
000 101
101 100
110 000
111 000

Ausgabe 1

0
1
3
2

Hinweis

• Erster Testfall: Die Lichter sind bereits alle aus.
• Zweiter Testfall: Wir schalten im ersten Zug den dritten Schalter um.
• Dritter Testfall: Wir schalten im ersten Zug den ersten Schalter, im zweiten Zug den zweiten Schalter und im dritten Zug erneut den zweiten Schalter um.
• Vierter Testfall: Wir schalten im ersten Zug den ersten Schalter und im zweiten Zug den dritten Schalter um.

Man kann zeigen, dass dies in jedem Fall die minimale benötigte Anzahl von Zügen ist.

Eingabe 2

1 10
1100010000 1000011000

Ausgabe 2

2

Hinweis

Man kann zeigen, dass $2$ Züge nötig sind, um alle Lichter auszuschalten.

• Wir schalten im ersten Zug den siebten Schalter um und im zweiten Zug erneut denselben Schalter.

Teilaufgaben

• Eingaben 3-5: $N \le 8$
• Eingaben 6-13: $N\le 18$
• Eingaben 14-20: keine zusätzlichen Beschränkungen.

Aufgabenautoren: William Yue, Eric Yang und Benjamin Qi