Little Cyan Fish hält eine Matrix $A$ mit $n$ Zeilen und $m$ Spalten in der Hand. Jedes Element in der Matrix kann Cyan oder Weiß sein. Wir verwenden das Zeichen C, um Cyan darzustellen, und das Zeichen W, um Weiß darzustellen. Der Einfachheit halber bezeichnet Little Cyan Fish das Element in der $i$-ten Zeile und $j$-ten Spalte ($1 \le i \le n, 1 \le j \le m$) der Matrix als $A_{i,j}$.

Little Cyan Fish kann die folgende Operation beliebig oft ausführen:

• Wähle ein Paar vertikal benachbarter oder horizontal benachbarter Zellen $A_{i,j}$ und $A_{k,l}$. Das heißt, $|i - k| + |j - l| = 1$.
• Vertausche $A_{i,j}$ und $A_{k,l}$.

Little Cyan Fish möchte die Matrix $A$ in eine andere gegebene Matrix $B$ umwandeln. Natürlich garantiert Little Cyan Fish, dass die Anzahl der Cyan-Elemente in Matrix $A$ gleich der Anzahl der Cyan-Elemente in der am Ende geforderten Matrix $B$ ist, sodass es eine Operationsfolge geben muss, die Little Cyan Fishs Anforderung erfüllt.

Du musst Little Cyan Fish dabei helfen, die minimale Anzahl an Operationen zu berechnen, die erforderlich ist, um seine Anforderung zu erfüllen.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile der Eingabe zwei ganze Zahlen $n$ und $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), welche die Anzahl der Zeilen und Spalten der Matrix darstellen.

Die nächsten $n$ Zeilen enthalten jeweils eine Zeichenkette der Länge $m$ (die nur die Zeichen C oder W enthält) und stellen die einzelnen Zeilen der Matrix $A$ dar.

Die nächsten $n$ Zeilen enthalten jeweils eine Zeichenkette der Länge $m$ (die nur die Zeichen C oder W enthält) und stellen die einzelnen Zeilen der Matrix $B$ dar. Es wird garantiert, dass die Anzahl der Zeichen C in Matrix $A$ und Matrix $B$ gleich ist (natürlich ist dann auch die Anzahl der Zeichen W gleich).

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer ganzen Zahl aus, welche die minimale Anzahl an Operationen darstellt, die Little Cyan Fish benötigt, um Matrix $A$ in Matrix $B$ umzuwandeln.

Beispiel

Eingabe 1

2
2 2
CW
WC
WC
CW
5 3
WWC
WCW
CWC
CCC
CCC
CCC
CCC
CCC
CWW
WWW

Ausgabe 1

2
16