Little Cyan Fishillä on kädessään matriisi $A$, jossa on $n$ riviä ja $m$ saraketta. Jokainen matriisin alkio voi olla syaani (Cyan) tai valkoinen (White). Käytämme merkkiä C kuvaamaan syaania ja merkkiä W kuvaamaan valkoista. Mukavuuden vuoksi Little Cyan Fish merkitsee matriisin $i$:nnen rivin ja $j$:nnen sarakkeen ($1 \le i \le n, 1 \le j \le m$) alkiota merkinnällä $A_{i,j}$.

Little Cyan Fish voi suorittaa seuraavan operaation mielivaltaisen monta kertaa:

• Valitse pari pystysuunnassa tai vaakasuunnassa vierekkäisiä soluja $A_{i,j}$ ja $A_{k,l}$. Toisin sanoen $|i - k| + |j - l| = 1$.
• Vaihda alkiot $A_{i,j}$ ja $A_{k,l}$ keskenään.

Little Cyan Fish haluaa muuntaa matriisin $A$ toiseksi annetuksi matriisiksi $B$. Tietenkin Little Cyan Fish takaa, että syaanien alkioiden lukumäärä matriisissa $A$ on yhtä suuri kuin syaanien alkioiden lukumäärä lopullisessa vaaditussa matriisissa $B$, joten on varmasti olemassa operaatioiden sarja, joka täyttää Little Cyan Fishin vaatimuksen.

Sinun tehtäväsi on auttaa Little Cyan Fishiä laskemaan pienin mahdollinen operaatioiden lukumäärä, joka tarvitaan hänen vaatimuksensa täyttämiseen.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), jotka kuvaavat matriisin rivien ja sarakkeiden lukumäärää.

Seuraavat $n$ riviä sisältävät kukin pituuden $m$ merkkijonon (joka sisältää vain merkkejä C tai W), jotka kuvaavat matriisin $A$ kunkin rivin.

Seuraavat $n$ riviä sisältävät kukin pituuden $m$ merkkijonon (joka sisältää vain merkkejä C tai W), jotka kuvaavat matriisin $B$ kunkin rivin. On taattu, että merkkien C lukumäärä matriisissa $A$ ja matriisissa $B$ on sama (luonnollisesti myös merkkien W lukumäärä on sama).

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, jolla on kokonaisluku: pienin operaatioiden lukumäärä, jonka Little Cyan Fish tarvitsee muuntaakseen matriisin $A$ matriisiksi $B$.

Esimerkki

Syöte 1

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

Tuloste 1

2
16