Coded Communication

When you send data over a distance — even a short one — the bits you transmit are sometimes flipped by accident. Such errors can be serious; imagine, for instance, misreading a critical instruction. To guard against them, most long-range and wireless communication uses error-correcting codes.

The simplest example that captures the idea is this: to send a single bit, '0' or '1', you can replace it with '000' or '111', respectively. Then, even if at most one bit is flipped in transit, the receiver can still recover whether the original bit was '0' or '1'. Codes based on plain duplication are not very efficient, and designing codes that add as few extra bits as possible while tolerating as many bit flips as possible is an active area of research.

Here you solve a much easier problem. Given a code someone has already designed and a received codeword, determine how many bits must have been flipped during transmission. More precisely, you are given $1 \le n \le 1000$ candidate strings $m_i$ of zeros and ones — the valid messages — each exactly $b$ bits long ($1 \le b \le 100$). You are also given the received message $r$, another bit string of $b$ bits. Find the minimum number $f$ of bits of $r$ you would need to flip in order to obtain some $m_i$.

The first line contains the number $K$ of data sets. The $K$ data sets follow, each of the form below.

The first line of a data set contains the two integers $n$ and $b$. This is followed by $n$ lines, each describing one valid codeword as a string of $b$ zeros and ones. After these $n$ lines comes one more line containing the received string $r$, again a string of $b$ zeros and ones.

For each data set, print Data Set x: on a line by itself, where $x$ is its number (starting from 1). On the next line, print the minimum distance $f$ between the received string and any valid codeword. Separate consecutive data sets with a single blank line.