Little Cyan Fish có một ma trận $A$ với $n$ hàng và $m$ cột. Mỗi phần tử trong ma trận có thể là Cyan (xanh lơ) hoặc White (trắng). Chúng ta sử dụng ký tự C để đại diện cho Cyan và ký tự W để đại diện cho White. Để thuận tiện, Little Cyan Fish ký hiệu phần tử ở hàng thứ $i$ và cột thứ $j$ ($1 \le i \le n, 1 \le j \le m$) của ma trận là $A_{i,j}$.
Little Cyan Fish có thể thực hiện thao tác sau bất kỳ số lần nào:
- Chọn một cặp ô kề cạnh theo chiều dọc hoặc chiều ngang $A_{i,j}$ và $A_{k,l}$. Nghĩa là, $|i - k| + |j - l| = 1$.
- Hoán đổi $A_{i,j}$ và $A_{k,l}$.
Little Cyan Fish muốn biến đổi ma trận $A$ thành một ma trận $B$ cho trước. Tất nhiên, Little Cyan Fish đảm bảo rằng số lượng phần tử Cyan trong ma trận $A$ bằng với số lượng phần tử Cyan trong ma trận đích $B$, vì vậy chắc chắn tồn tại một chuỗi thao tác thỏa mãn yêu cầu của Little Cyan Fish.
Bạn cần giúp Little Cyan Fish tính toán số lượng thao tác tối thiểu cần thiết để hoàn thành yêu cầu của mình.
Dữ liệu vào
Có nhiều bộ dữ liệu kiểm thử. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T$), biểu thị số lượng bộ dữ liệu kiểm thử.
Đối với mỗi bộ dữ liệu kiểm thử, dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), biểu thị số hàng và số cột của ma trận.
$n$ dòng tiếp theo, mỗi dòng chứa một chuỗi có độ dài $m$ (chỉ chứa các ký tự C hoặc W), biểu thị từng hàng của ma trận $A$.
$n$ dòng tiếp theo, mỗi dòng chứa một chuỗi có độ dài $m$ (chỉ chứa các ký tự C hoặc W), biểu thị từng hàng của ma trận $B$. Đảm bảo rằng số lượng ký tự C trong ma trận $A$ và ma trận $B$ là như nhau (tất nhiên, số lượng ký tự W cũng sẽ như nhau).
Đảm bảo rằng tổng $n$ trên tất cả các bộ dữ liệu kiểm thử không vượt quá $10^5$.
Dữ liệu ra
Đối với mỗi bộ dữ liệu kiểm thử, in ra một dòng duy nhất với một số nguyên, biểu thị số lượng thao tác tối thiểu cần thiết để Little Cyan Fish biến đổi ma trận $A$ thành ma trận $B$.
Ví dụ
Dữ liệu vào 1
2 2 2 CW WC WC CW 5 3 WWC WCW CWC CCC CCC CCC CCC CCC CWW WWW
Dữ liệu ra 1
2 16