Бесі хоче піти спати, їй потрібно вимкнути усі лампи. Як це зробити?

У Бесі є два бітові рядки довжиною \(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\).

Формат вихідних даних

Для кожної пари виведіть мінімальну кількість необхідних ходів, щоб вимкнути всі лампочки.

Приклад вхідних даних

4 3
000 101
101 100
110 000
111 000

Приклад вихідних даних

0
1
3
2

• Перший підтест: лампочки вже вимкнені.
• Другий підтест: перемикаємо третій перемикач на першому ході.
• Третій підтест: перемикаємо перший перемикач на першому ходу, другий перемикач на другому ходу та знову другий перемикач на третьому ходу.
• Четвертий підтест: ми перемикаємо перший перемикач на першому ходу та третій перемикач на другому ході.

В кожному разі можна довести, що це мінімально необхідна кількість ходів.

Приклад вхідних даних

1 10
1100010000 1000011000

Приклад вихідних даних

2

Можна довести лише два ходи достатньо, щоб вимкнути всі лампочки.

• Перемикаємо 7-й перемикач на першому ходу і потім його ж на другому ходу.

ОЦІНЮВАННЯ:

• Тести 3-5: \(N \le 8\)
• Тести 6-13: \(N\le 18\)
• Тести 14-20: Немає додаткових обмежень.