Little Cyan Fish possède une matrice $A$ avec $n$ lignes et $m$ colonnes. Chaque élément de la matrice peut être Cyan ou Blanc. Nous utilisons le caractère C pour représenter Cyan, et le caractère W pour représenter Blanc. Par commodité, Little Cyan Fish désigne l'élément de la $i$-ième ligne et de la $j$-ième colonne ($1 \le i \le n, 1 \le j \le m$) de la matrice par $A_{i,j}$.

Little Cyan Fish peut effectuer l'opération suivante un nombre quelconque de fois :

• Choisir une paire de cellules $A_{i,j}$ et $A_{k,l}$ verticalement ou horizontalement adjacentes. C'est-à-dire, $|i - k| + |j - l| = 1$.
• Échanger $A_{i,j}$ et $A_{k,l}$.

Little Cyan Fish souhaite transformer la matrice $A$ en une autre matrice donnée $B$. Bien entendu, Little Cyan Fish garantit que le nombre d'éléments Cyan dans la matrice $A$ est égal au nombre d'éléments Cyan dans la matrice finale requise $B$, il doit donc exister un schéma d'opérations qui satisfait l'exigence de Little Cyan Fish.

Vous devez aider Little Cyan Fish à calculer le nombre minimum d'opérations requises pour satisfaire son exigence.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier unique $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne de l'entrée contient deux entiers $n$ et $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), représentant le nombre de lignes et de colonnes de la matrice.

Les $n$ lignes suivantes, contenant chacune une chaîne de longueur $m$ (ne contenant que les caractères C ou W), représentent chaque ligne de la matrice $A$.

Les $n$ lignes suivantes, contenant chacune une chaîne de longueur $m$ (ne contenant que les caractères C ou W), représentent chaque ligne de la matrice $B$. Il est garanti que le nombre de caractères C dans la matrice $A$ et dans la matrice $B$ est le même (naturellement, le nombre de caractères W sera également le même).

Il est garanti que la somme de $n$ sur tous les cas de test n'excède pas $10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne avec un entier, représentant le nombre minimum d'opérations requises pour que Little Cyan Fish transforme la matrice $A$ en matrice $B$.

Exemples

Entrée 1

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

Sortie 1

2
16