Little Cyan Fish has a matrix $A$ with $n$ rows and $m$ columns in his hand. Each element in the matrix can be Cyan or White. We use the character C to represent Cyan, and the character W to represent White. For convenience, Little Cyan Fish denotes the element in the $i$-th row and $j$-th column ($1 \le i \le n, 1 \le j \le m$) of the matrix as $A_{i,j}$.

Little Cyan Fish can perform the following operation any number of times:

• Choose a pair of vertically adjacent or horizontally adjacent cells $A_{i,j}$ and $A_{k,l}$. That is, $|i - k| + |j - l| = 1$.
• Swap $A_{i,j}$ and $A_{k,l}$.

Little Cyan Fish wants to transform matrix $A$ into another given matrix $B$. Of course, Little Cyan Fish guarantees that the number of Cyan elements in matrix $A$ is equal to the number of Cyan elements in the final required matrix $B$, so there must exist an operation scheme that satisfies Little Cyan Fish’s requirement.

You need to help Little Cyan Fish calculate the minimum number of operations required to complete his requirement.

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T$), indicating the number of test cases.

For each test case, the first line of the input contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le 6$), representing the number of rows and columns of the matrix.

The next $n$ lines, each containing a string of length $m$ (only containing characters C or W), representing each row of matrix $A$.

The next $n$ lines, each containing a string of length $m$ (only containing characters C or W), representing each row of matrix $B$. It is guaranteed that the number of character Cs in matrix $A$ and matrix $B$ are the same (naturally, the number of character Ws will also be the same).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single line with an integer, representing the minimum number of operations required for Little Cyan Fish to transform matrix $A$ into matrix $B$.

Examples

Input 1

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

Output 1

2
16