Little Cyan Fish memiliki sebuah matriks $A$ dengan $n$ baris dan $m$ kolom di tangannya. Setiap elemen dalam matriks dapat berwarna Sian (Cyan) atau Putih (White). Kita menggunakan karakter C untuk menyatakan Sian, dan karakter W untuk menyatakan Putih. Untuk kemudahan, Little Cyan Fish menuliskan elemen pada baris ke-$i$ dan kolom ke-$j$ ($1 \le i \le n, 1 \le j \le m$) dari matriks tersebut sebagai $A_{i,j}$.

Little Cyan Fish dapat melakukan operasi berikut berapa kali pun:

• Pilih sepasang sel yang bersebelahan secara vertikal atau bersebelahan secara horizontal $A_{i,j}$ dan $A_{k,l}$. Artinya, $|i - k| + |j - l| = 1$.
• Tukar $A_{i,j}$ dan $A_{k,l}$.

Little Cyan Fish ingin mengubah matriks $A$ menjadi matriks lain $B$ yang diberikan. Tentu saja, Little Cyan Fish menjamin bahwa banyaknya elemen Sian pada matriks $A$ sama dengan banyaknya elemen Sian pada matriks akhir $B$ yang diinginkan, sehingga pasti terdapat skema operasi yang memenuhi keinginan Little Cyan Fish.

Anda perlu membantu Little Cyan Fish menghitung jumlah operasi minimum yang diperlukan untuk menyelesaikan keinginannya.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama dari masukan berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 10^5, 1 \le m \le 6$), yang menyatakan banyaknya baris dan kolom dari matriks.

$n$ baris berikutnya masing-masing berisi sebuah string dengan panjang $m$ (hanya berisi karakter C atau W), yang menyatakan setiap baris dari matriks $A$.

$n$ baris berikutnya masing-masing berisi sebuah string dengan panjang $m$ (hanya berisi karakter C atau W), yang menyatakan setiap baris dari matriks $B$. Dijamin bahwa banyaknya karakter C pada matriks $A$ dan matriks $B$ adalah sama (tentu saja, banyaknya karakter W juga akan sama).

Dijamin bahwa jumlah dari $n$ di semua kasus uji tidak melebihi $10^5$.

Keluaran

Untuk setiap kasus uji, cetak satu baris berisi sebuah bilangan bulat, yang menyatakan jumlah operasi minimum yang diperlukan bagi Little Cyan Fish untuk mengubah matriks $A$ menjadi matriks $B$.

Contoh

Masukan 1

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

Keluaran 1

2
16