ל-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