Bessie רוצה ללכת לישון, אבל האורות בחווה משאירים אותה ערה. איך היא יכולה לכבות אותם?

ל-Bessie יש שתי מחרוזות ביטים באורך $N$ ($2\le N\le 20$), המייצגות רצף של אורות ורצף של מתגים, בהתאמה. כל אור דולק (1) או כבוי (0). כל מתג פעיל (1) או לא פעיל (0).

מהלך מורכב מרצף הפעולות הבא:

1. להפוך את מצבו של מתג אחד בדיוק (להפעיל אותו אם אינו פעיל, או להפך).
2. עבור כל מתג פעיל, להפוך את מצבו של האור המתאים (לכבות אותו אם הוא דולק, או להפך).
3. להזיז את המתגים באופן מחזורי מקום אחד ימינה. ליתר דיוק, אם מחרוזת הביטים של המתגים היא בתחילה $s_0s_1\dots s_{N-1}$, היא הופכת ל-$s_{N-1}s_0s_1\dots s_{N-2}$.

עבור $T$ מופעים של הבעיה לעיל ($1\le T\le 2\cdot 10^5$), חשבו את מספר המהלכים המינימלי הדרוש כדי לכבות את כל האורות.

קלט

השורה הראשונה מכילה את $T$ ו-$N$.

כל אחת מ-$T$ השורות הבאות מכילה זוג מחרוזות ביטים באורך $N$.

פלט

עבור כל זוג, הדפיסו את מספר המהלכים המינימלי הדרוש כדי לכבות את כל האורות.

דוגמאות

קלט 1

4 3
000 101
101 100
110 000
111 000

פלט 1

0
1
3
2

הערה

• מקרה הבדיקה הראשון: כל האורות כבר כבויים.
• מקרה הבדיקה השני: אנו הופכים את מצבו של המתג השלישי במהלך הראשון.
• מקרה הבדיקה השלישי: אנו הופכים את מצבו של המתג הראשון במהלך הראשון, של המתג השני במהלך השני, ושוב של המתג השני במהלך השלישי.
• מקרה הבדיקה הרביעי: אנו הופכים את מצבו של המתג הראשון במהלך הראשון ושל המתג השלישי במהלך השני.

אפשר להראות שבכל מקרה זהו מספר המהלכים המינימלי הדרוש.

קלט 2

1 10
1100010000 1000011000

פלט 2

2

הערה

אפשר להראות שנדרשים $2$ מהלכים כדי לכבות את כל האורות.

• אנו הופכים את מצבו של המתג השביעי במהלך הראשון, ואז שוב במהלך השני.

תתי־משימות

• קלטים 3-5: $N \le 8$
• קלטים 6-13: $N\le 18$
• קלטים 14-20: אין מגבלות נוספות.

מחברי הבעיה: William Yue, Eric Yang ו-Benjamin Qi