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