Little Cyan Fish posiada macierz $A$ o $n$ wierszach i $m$ kolumnach. Każdy element w macierzy może być cyjanowy (Cyan) lub biały (White). Używamy znaku C do oznaczenia koloru cyjanowego, a znaku W do oznaczenia koloru białego. Dla wygody, Little Cyan Fish oznacza element w $i$-tym wierszu i $j$-tej kolumnie ($1 \le i \le n, 1 \le j \le m$) macierzy jako $A_{i,j}$.

Little Cyan Fish może wykonać dowolną liczbę razy następującą operację: Wybrać parę pionowo lub poziomo sąsiadujących komórek $A_{i,j}$ oraz $A_{k,l}$. Oznacza to, że $|i - k| + |j - l| = 1$. Zamienić miejscami $A_{i,j}$ oraz $A_{k,l}$.

Little Cyan Fish chce przekształcić macierz $A$ w inną, zadaną macierz $B$. Oczywiście, Little Cyan Fish gwarantuje, że liczba elementów cyjanowych w macierzy $A$ jest równa liczbie elementów cyjanowych w końcowej wymaganej macierzy $B$, więc musi istnieć schemat operacji spełniający wymagania Little Cyan Fish.

Musisz pomóc Little Cyan Fish obliczyć minimalną liczbę operacji wymaganych do spełnienia jego wymagań.

Wejście

Dostępnych jest wiele przypadków testowych. Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego, pierwsza linia wejścia zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), reprezentujące liczbę wierszy i kolumn macierzy.

Kolejne $n$ linii, z których każda zawiera ciąg znaków o długości $m$ (zawierający tylko znaki C lub W), reprezentuje każdy wiersz macierzy $A$.

Kolejne $n$ linii, z których każda zawiera ciąg znaków o długości $m$ (zawierający tylko znaki C lub W), reprezentuje każdy wiersz macierzy $B$. Gwarantuje się, że liczba znaków C w macierzy $A$ i macierzy $B$ jest taka sama (naturalnie, liczba znaków W również będzie taka sama).

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w pojedynczej linii liczbę całkowitą, reprezentującą minimalną liczbę operacji wymaganych przez Little Cyan Fish do przekształcenia macierzy $A$ w macierz $B$.

Przykład

Wejście 1

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

Wyjście 1

2
16