**Замечание: Время на тест в этой задаче 4s, в два раза больше обычного.**
Беси хочет пойти спать, ей нужно выключить все лампы. Как это сделать?
У Беси есть две битовые строки длиной \(N\) (\(2\le N\le 20\)), представляющие
последовательность лампочек и переключателей, соответственно. Каждая лампочка
включена(1) или выключена(0). Каждый переключатель активен(1) или неактивен(0).
Один *шаг* состоит из следующей последовательности операций:
- Переключить ровно один переключатель (сделать активным, если он неактивный
или наоборот).
- Для каждого активного переключателя переключить состояние соответствующей
лампочки (выключить, если она была включена или наоборот).
- Циклически сдвинуть переключатели вправо на один. А именно, если
битовая строка соответствующая переключателям была изначально \(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\)) примеров описанной выше проблемы
посчитайте минимальное количество ходов выключить все лампочки.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(T\) и
\(N\).
Каждая из следующих \(T\) строк содержит пару битовых строк длиной \(N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждой пары выведите минимальное количество требуемых ходов, чтобы
выключить все лампочки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
000 101
101 100
110 000
111 000
|
0
1
3
2
|