Little Cyan Fish har en matris $A$ med $n$ rader och $m$ kolumner i sin hand. Varje element i matrisen kan vara cyanfärgat (Cyan) eller vitt (White). Vi använder tecknet C för att representera cyan, och tecknet W för att representera vitt. För enkelhetens skull betecknar Little Cyan Fish elementet på den $i$:te raden och $j$:te kolumnen ($1 \le i \le n, 1 \le j \le m$) i matrisen som $A_{i,j}$.

Little Cyan Fish kan utföra följande operation valfritt antal gånger:

• Välj ett par vertikalt intilliggande eller horisontellt intilliggande celler $A_{i,j}$ och $A_{k,l}$. Det vill säga, $|i - k| + |j - l| = 1$.
• Byt plats på $A_{i,j}$ och $A_{k,l}$.

Little Cyan Fish vill omvandla matris $A$ till en annan given matris $B$. Naturligtvis garanterar Little Cyan Fish att antalet cyanfärgade element i matris $A$ är lika med antalet cyanfärgade element i den slutliga önskade matrisen $B$, så det måste finnas en operationsföljd som uppfyller Little Cyan Fishs krav.

Du behöver hjälpa Little Cyan Fish att beräkna det minsta antalet operationer som krävs för att uppfylla hans krav.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett enda heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden i indata två heltal $n$ och $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), som representerar antalet rader och kolumner i matrisen.

De följande $n$ raderna innehåller var och en en sträng med längden $m$ (som endast innehåller tecknen C eller W), vilka representerar varje rad i matris $A$.

De följande $n$ raderna innehåller var och en en sträng med längden $m$ (som endast innehåller tecknen C eller W), vilka representerar varje rad i matris $B$. Det garanteras att antalet tecken C i matris $A$ och matris $B$ är detsamma (naturligtvis kommer även antalet tecken W att vara detsamma).

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^5$.

Utdata

För varje testfall, skriv ut en enda rad med ett heltal som representerar det minsta antalet operationer som krävs för att Little Cyan Fish ska omvandla matris $A$ till matris $B$.

Exempel

Indata 1

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

Utdata 1

2
16