Little Cyan Fish er með fylki $A$ með $n$ röðum og $m$ dálkum í hendinni. Hvert stak í fylkinu getur verið blágrænt (Cyan) eða hvítt (White). Við notum stafinn C til að tákna blágrænt og stafinn W til að tákna hvítt. Til hægðarauka táknar Little Cyan Fish stakið í $i$-tu röð og $j$-ta dálki ($1 \le i \le n, 1 \le j \le m$) fylkisins sem $A_{i,j}$.

Little Cyan Fish getur framkvæmt eftirfarandi aðgerð hversu oft sem er:

• Velja par af lóðrétt eða lárétt aðliggjandi reitum $A_{i,j}$ og $A_{k,l}$. Það er, $|i - k| + |j - l| = 1$.
• Víxla $A_{i,j}$ og $A_{k,l}$.

Little Cyan Fish vill breyta fylkinu $A$ í annað gefið fylki $B$. Að sjálfsögðu ábyrgist Little Cyan Fish að fjöldi blágrænna staka í fylkinu $A$ sé jafn fjölda blágrænna staka í lokafylkinu $B$, þannig að það hlýtur að vera til aðgerðaáætlun sem uppfyllir kröfu Little Cyan Fish.

Þú þarft að hjálpa Little Cyan Fish að reikna út lágmarksfjölda aðgerða sem þarf til að uppfylla kröfu hans.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan í inntakinu tvær heiltölur $n$ og $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), sem tákna fjölda raða og dálka í fylkinu.

Næstu $n$ línur innihalda hver um sig streng af lengd $m$ (sem inniheldur aðeins stafina C eða W), sem táknar hverja röð í fylkinu $A$.

Næstu $n$ línur innihalda hver um sig streng af lengd $m$ (sem inniheldur aðeins stafina C eða W), sem táknar hverja röð í fylkinu $B$. Það er tryggt að fjöldi stafanna C í fylki $A$ og fylki $B$ sé sá sami (eðlilega verður fjöldi stafanna W líka sá sami).

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skaltu prenta eina línu með heiltölu, sem táknar lágmarksfjölda aðgerða sem Little Cyan Fish þarf til að breyta fylkinu $A$ í fylkið $B$.

Dæmi

Inntak 1

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

Úttak 1

2
16