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