Little Cyan Fish tiene una matriz $A$ con $n$ filas y $m$ columnas en sus manos. Cada elemento de la matriz puede ser Cian o Blanco. Usamos el carácter C para representar Cian y el carácter W para representar Blanco. Por conveniencia, Little Cyan Fish denota el elemento en la fila $i$-ésima y la columna $j$-ésima ($1 \le i \le n, 1 \le j \le m$) de la matriz como $A_{i,j}$.

Little Cyan Fish puede realizar la siguiente operación cualquier número de veces:

• Elegir un par de celdas $A_{i,j}$ y $A_{k,l}$ adyacentes vertical u horizontalmente. Es decir, $|i - k| + |j - l| = 1$.
• Intercambiar $A_{i,j}$ y $A_{k,l}$.

Little Cyan Fish desea transformar la matriz $A$ en otra matriz dada $B$. Por supuesto, Little Cyan Fish garantiza que el número de elementos Cian en la matriz $A$ es igual al número de elementos Cian en la matriz final requerida $B$, por lo que debe existir un esquema de operaciones que satisfaga el requisito de Little Cyan Fish.

Debes ayudar a Little Cyan Fish a calcular el número mínimo de operaciones necesarias para completar su requisito.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un único entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea de la entrada contiene dos enteros $n$ y $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), que representan el número de filas y columnas de la matriz.

Las siguientes $n$ líneas, cada una conteniendo una cadena de longitud $m$ (que solo contiene los caracteres C o W), representan cada fila de la matriz $A$.

Las siguientes $n$ líneas, cada una conteniendo una cadena de longitud $m$ (que solo contiene los caracteres C o W), representan cada fila de la matriz $B$. Se garantiza que el número de caracteres C en la matriz $A$ y en la matriz $B$ es el mismo (naturalmente, el número de caracteres W también será el mismo).

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $10^5$.

Salida

Para cada caso de prueba, imprime una sola línea con un entero, que represente el número mínimo de operaciones necesarias para que Little Cyan Fish transforme la matriz $A$ en la matriz $B$.

Ejemplos

Entrada 1

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

Salida 1

2
16