يمتلك 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