У Little Cyan Fish есть матрица $A$ из $n$ строк и $m$ столбцов. Каждый элемент матрицы может быть либо голубым (Cyan), либо белым (White). Мы используем символ C для обозначения голубого цвета, а символ W — для белого. Для удобства Little Cyan Fish обозначает элемент в $i$-й строке и $j$-м столбце ($1 \le i \le n, 1 \le j \le m$) матрицы как $A_{i,j}$.

Little Cyan Fish может выполнять следующую операцию любое количество раз: Выбрать пару вертикально или горизонтально соседних ячеек $A_{i,j}$ и $A_{k,l}$. То есть $|i - k| + |j - l| = 1$. Поменять местами $A_{i,j}$ и $A_{k,l}$.

Little Cyan Fish хочет преобразовать матрицу $A$ в другую заданную матрицу $B$. Разумеется, Little Cyan Fish гарантирует, что количество голубых элементов в матрице $A$ равно количеству голубых элементов в итоговой требуемой матрице $B$, поэтому всегда существует схема операций, удовлетворяющая требованию Little Cyan Fish.

Вам нужно помочь Little Cyan Fish вычислить минимальное количество операций, необходимое для выполнения его требования.

Входные данные

Имеется несколько тестовых случаев. Первая строка входных данных содержит единственное целое число $T$ ($1 \le T$), указывающее количество тестовых случаев.

Для каждого тестового случая первая строка содержит два целых числа $n$ и $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), представляющих количество строк и столбцов матрицы.

Следующие $n$ строк, каждая из которых содержит строку длины $m$ (состоящую только из символов C или W), представляют каждую строку матрицы $A$.

Следующие $n$ строк, каждая из которых содержит строку длины $m$ (состоящую только из символов C или W), представляют каждую строку матрицы $B$. Гарантируется, что количество символов C в матрице $A$ и матрице $B$ одинаково (естественно, количество символов W также будет одинаковым).

Гарантируется, что сумма $n$ по всем тестовым случаям не превышает $10^5$.

Выходные данные

Для каждого тестового случая выведите одну строку с целым числом, представляющим минимальное количество операций, необходимое Little Cyan Fish для преобразования матрицы $A$ в матрицу $B$.

Примеры

Входные данные 1

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

Выходные данные 1

2
16