C. Битовая сортировка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Девочке Софии очень нравится бинарная запись числа. Однажды вечером она выписывала случайные числа. По счастливой случайности все эти числа были $$$k$$$-битными, то есть для любого числа $$$a_i$$$, которое София написала, выполняется $$$0 \le a_i \lt 2^k$$$. После этого ее заинтересовал вопрос: если она может поменять значение одного бита в одном из чисел на противоположное, то за какое минимальное количество подобных действий она сможет отсортировать свой список по неубыванию?

Входные данные

В первой строке вводится число $$$t$$$ $$$(1 \le t \le 100)$$$ — количество наборов входных данных. Для каждого набора входных данных вводятся числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 100, 1 \le k \le 30)$$$. В следующих $$$n$$$ строках вводятся $$$k$$$-битные целые числа $$$a_i$$$, которые написала София $$$(0 \le a_i \lt 2^k)$$$. Числа записаны в двоичной системе счисления (от старших разрядов к младшим) с ровно $$$k$$$ битами.

Гарантируется, что сумма n по всем наборам входных данных не превосходит 100.

Выходные данные

Для каждого набора входных данных выведите одно число — минимальное количество действий, необходимых для сортировки массива.

Система оценки

Решения, работающие корректно при $$$n \le 2$$$ получат не менее 10% баллов.

Решения, работающие корректно при $$$n \le 10$$$ получат не менее 40% баллов.

Решения, работающие корректно при $$$k \le 10$$$ получат не менее 40% баллов.

Пример
Входные данные
4
3 3
000
101
010
3 3
000
111
010
3 3
100
111
010
1 1
0
Выходные данные
1
2
2
0
Примечание

В первом наборе данных достаточно изменить первый бит во втором числе. Тогда получится последовательность 000, 001, 010, что в десятичной системе будет 0,1,2.

Во втором наборе данных можно изменить первые два бита второго числа. Тогда получится последовательность 000, 001, 010, что в десятичной системе будет 0, 1, 2.

Во третьем наборе данных можно изменить первый и последний бит последнего числа. Тогда получится последовательность 100, 111, 111, что в десятичной системе будет 4, 7, 7.

В четвертом примере ничего менять не надо, так как последовательность уже неубывающая.