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

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

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

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

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

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

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

В задаче 20 тестов, за каждый из которых вы получите 5 баллов. Решения, работающие корректно при n ⩽ 2, получат не менее 10 баллов.

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

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