Little Cyan Fish ha in mano una matrice $A$ con $n$ righe e $m$ colonne. Ogni elemento della matrice può essere Ciano (Cyan) o Bianco (White). Usiamo il carattere C per rappresentare il Ciano e il carattere W per rappresentare il Bianco. Per comodità, Little Cyan Fish indica l'elemento nella $i$-esima riga e $j$-esima colonna ($1 \le i \le n, 1 \le j \le m$) della matrice come $A_{i,j}$.

Little Cyan Fish può eseguire la seguente operazione un numero qualsiasi di volte:

• Scegliere una coppia di celle adiacenti verticalmente o adiacenti orizzontalmente $A_{i,j}$ e $A_{k,l}$. Cioè, $|i - k| + |j - l| = 1$.
• Scambiare $A_{i,j}$ e $A_{k,l}$.

Little Cyan Fish vuole trasformare la matrice $A$ in un'altra matrice data $B$. Naturalmente, Little Cyan Fish garantisce che il numero di elementi Ciano nella matrice $A$ è uguale al numero di elementi Ciano nella matrice finale richiesta $B$, quindi deve esistere una sequenza di operazioni che soddisfa la richiesta di Little Cyan Fish.

Devi aiutare Little Cyan Fish a calcolare il numero minimo di operazioni necessarie per soddisfare la sua richiesta.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga dell'input contiene due interi $n$ e $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), che rappresentano il numero di righe e di colonne della matrice.

Le successive $n$ righe contengono ciascuna una stringa di lunghezza $m$ (contenente solo i caratteri C o W), che rappresenta ciascuna riga della matrice $A$.

Le successive $n$ righe contengono ciascuna una stringa di lunghezza $m$ (contenente solo i caratteri C o W), che rappresenta ciascuna riga della matrice $B$. È garantito che il numero di caratteri C nella matrice $A$ e nella matrice $B$ sia lo stesso (naturalmente, anche il numero di caratteri W sarà lo stesso).

È garantito che la somma di $n$ su tutti i casi di test non supera $10^5$.

Output

Per ogni caso di test, stampa una singola riga con un intero, che rappresenta il numero minimo di operazioni necessarie a Little Cyan Fish per trasformare la matrice $A$ nella matrice $B$.

Esempio

Input 1

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

Output 1

2
16