Little Cyan Fish har en matrise $A$ med $n$ rader og $m$ kolonner i hånden sin. Hvert element i matrisen kan være cyanfarget (Cyan) eller hvitt (White). Vi bruker tegnet C for å representere cyan, og tegnet W for å representere hvitt. For enkelhets skyld betegner Little Cyan Fish elementet i den $i$-te raden og $j$-te kolonnen ($1 \le i \le n, 1 \le j \le m$) i matrisen som $A_{i,j}$.

Little Cyan Fish kan utføre følgende operasjon så mange ganger han vil:

• Velg et par vertikalt tilstøtende eller horisontalt tilstøtende celler $A_{i,j}$ og $A_{k,l}$. Det vil si, $|i - k| + |j - l| = 1$.
• Bytt om på $A_{i,j}$ og $A_{k,l}$.

Little Cyan Fish ønsker å gjøre om matrise $A$ til en annen gitt matrise $B$. Selvfølgelig garanterer Little Cyan Fish at antallet cyanfargede elementer i matrise $A$ er lik antallet cyanfargede elementer i den endelige ønskede matrisen $B$, så det må finnes en operasjonsplan som oppfyller kravet til Little Cyan Fish.

Du må hjelpe Little Cyan Fish med å beregne det minste antallet operasjoner som kreves for å fullføre kravet hans.

Inndata

Det er flere testtilfeller. Den første linjen av inndataene inneholder et enkelt heltall $T$ ($1 \le T$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen av inndataene to heltall $n$ og $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), som representerer antallet rader og kolonner i matrisen.

De neste $n$ linjene inneholder hver en streng med lengde $m$ (som kun inneholder tegnene C eller W), som representerer hver rad i matrise $A$.

De neste $n$ linjene inneholder hver en streng med lengde $m$ (som kun inneholder tegnene C eller W), som representerer hver rad i matrise $B$. Det er garantert at antallet tegn C i matrise $A$ og matrise $B$ er det samme (naturligvis vil også antallet tegn W være det samme).

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $10^5$.

Utdata

For hvert testtilfelle, skriv ut én enkelt linje med et heltall, som representerer det minste antallet operasjoner som kreves for at Little Cyan Fish skal gjøre om matrise $A$ til matrise $B$.

Eksempel

Inndata 1

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

Utdata 1

2
16