Угадайка - любимая игра Алисы для двух игроков. В этой игре используется колода, содержащая несколько карт, на каждой из которых записана последовательность нулей и единиц. Длины всех последовательностей на карточках равны.

В игре "Угадайка" Алиса случайным образом выбирает карту из колоды, а другой игрок пытается определить, какая последовательность записана на карте, задавая Алисе ряд вопросов в форме "Какая i - ая цифра последовательности? После каждого такого вопроса Алиса отвечает (правдиво) на вопрос, а второй игрок может задать другой вопрос или попытаться угадать последовательность на карте. Второй игрок может предоставить свою догадку только один раз, поэтому если его догадка верна, он выигрывает, в противном случае он проигрывает.

Алиса предложила вам сыграть в игру и выиграть, задавая как можно меньше вопросов.

Зная все последовательности, указанные на карточках, найдите минимальное количество вопросов, необходимых для однозначного определения последовательности, независимо от того, какую карту выберет Алиса.

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

Первая строка содержит количество тестов z (1 ≤ z ≤ 20). Далее следует описание тестов.

Первая строка каждого теста содержит два целых числа n и k (1 ≤ n ≤ 2k, 1 ≤ k ≤ 13) - количество карт и длину всех последовательностей на картах. Каждая из следующих n строк имеет длину k и состоит из нулей и единиц, описывая последовательность на одной карте. Никакие две последовательности в одном тесте не являются одинаковыми.

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

Для каждого теста выведите одно целое число: минимальное количество вопросов, которое второй игрок должен задать, чтобы выиграть игру.