19249번 - Guessing Game 다국어

Guessing Game is Alice's favorite game for two players. This game is played with a deck containing a number of cards, each having a sequence of zeroes and ones written on it. The lengths of all sequences on the cards are equal.

In Guessing Game Alice picks at random a card from the deck, and the other player attempts to determine what sequence is written on the card, by asking Alice a series of questions of the form "What is the $i$-th digit of the sequence?". After each such question Alice answers (truthfully) to the question, and the second player may ask another question, or try to guess the sequence on the card. The second player can only guess once, so if his guess is correct, he wins, otherwise he loses.

Alice challenged you to play the game and win by asking as few questions as possible.

Given all the sequences that appear on the cards, find the minimal number of questions needed to uniquely determine the sequence, no matter what card is picked by Alice.

The first line of input contains the number of test cases $z$ ($1 \leq z \leq 20$). The descriptions of the test cases follow.

The first line of every test case contains two integers $n, k$ ($1 \leq n \leq 2^k; 1 \leq k \leq 13$), denoting the number of cards and the length of all sequences appearing on the cards respectively. Each of the following $n$ lines contains a string of length $k$ consisting of zeroes and ones, describing the sequence on one card. No two sequences in a test case are equal. 

For each test case output one integer: the minimal number of questions the second player has to ask to win the game.