Little Cyan Fish는 $n$행 $m$열의 행렬 $A$를 가지고 있습니다. 행렬의 각 원소는 Cyan(청록색) 또는 White(흰색)일 수 있습니다. 우리는 Cyan을 나타내기 위해 문자 C를 사용하고, White를 나타내기 위해 문자 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$에 있는 Cyan 원소의 개수가 최종적으로 요구되는 행렬 $B$의 Cyan 원소 개수와 같음을 보장하므로, Little Cyan Fish의 요구사항을 만족하는 연산 계획은 반드시 존재합니다.

Little Cyan Fish가 요구사항을 완료하기 위해 필요한 최소 연산 횟수를 계산하도록 도와주세요.

입력

입력은 여러 개의 테스트 케이스로 구성됩니다. 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T(1 \le T)$가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 행렬의 행과 열의 수를 나타내는 두 정수 $n$과 $m(1 \le n \le 10^5, 1 \le m \le 6)$이 주어집니다.

다음 $n$개의 줄에는 행렬 $A$의 각 행을 나타내는 길이 $m$의 문자열(C 또는 W만 포함)이 주어집니다.

그다음 $n$개의 줄에는 행렬 $B$의 각 행을 나타내는 길이 $m$의 문자열(C 또는 W만 포함)이 주어집니다. 행렬 $A$와 행렬 $B$에 포함된 C의 개수는 동일함이 보장됩니다(당연히 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