eolymp
bolt
Try our new interface for solving problems
Məsələlər

Угадайка

Угадайка

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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

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

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

Giriş verilənləri

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

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
1
4 3
000
100
010
011
Çıxış verilənləri #1
2
Mənbə 2018 Петрозаводск, Зима, Jagiellonian U, Январь 30, Задача E