# Problem C

Codes

Error correcting codes are used in a wide variety of
applications ranging from satellite communication to music CDs.
The idea is to encode a binary string of length $k$ as a binary string of length
$n>k$, called a
*codeword*, in such a way that even if some bit(s) of
the encoding are corrupted (if you scratch on your CD for
instance), the original $k$-bit string can still be recovered.
There are three important parameters associated with an error
correcting code: the *length* of codewords ($n$), the *dimension*
($k$) which is the length
of the unencoded strings, and finally the *minimum
distance* ($d$) of the
code.

Distance between two codewords is measured as Hamming distance, i.e., the number of positions in which the codewords differ: $0010$ and $0100$ are at distance $2$. The minimum distance of the code is the distance between the two different codewords that are closest to each other.

Linear codes are a simple type of error correcting codes with several nice properties. One of them is that the minimum distance is the smallest distance any non-zero codeword has to the zero codeword (the codeword consisting of $n$ zeros always belongs to a linear code of length $n$).

Another nice property of linear codes of length $n$ and dimension $k$ is that they can be described by an $n\times k$ generator matrix of zeros and ones. Encoding a $k$-bit string is done by viewing it as a column vector and multiplying it by the generator matrix. The example below shows a generator matrix and how the string $1001$ is encoded.

\[ \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{array} \right) \left(\begin{array}{c} 1\\ 0\\ 0\\ 1\end{array}\right) = \left(\begin{array}{c} 1\\ 0\\ 0\\ 1 \\ 1\\ 0\\ 0 \end{array}\right) \]Matrix multiplication is done as usual except that addition is done modulo $2$ (i.e., $0+1=1+0=1$ and $0+0=1+1=0$). The set of codewords of this code is then simply all vectors that can be obtained by encoding all $k$-bit strings in this way.

Write a program to calculate the minimum distance for several linear error correcting codes of length at most $30$ and dimension at most $15$. Each code will be given as a generator matrix.

## Input

You will be given several generator matrices as input. The first line contains an integer $1 \le T\leq 40$ indicating the number of test cases. The first line of each test case gives the parameters $n$ and $k$ where $2\leq n\leq 30$, $1 \leq k\leq 15$ and $n > k$, as two integers separated by a single space. The following $n$ lines describe a generator matrix. Each line is a row of the matrix and has $k$ space separated entries that are $0$ or $1$. You may assume that for any generator matrix in the input, there will never be two different unencoded strings which give the same codeword.

## Output

For each generator matrix output a single line with the minimum distance of the corresponding linear code.

Sample Input 1 | Sample Output 1 |
---|---|

2 7 4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 3 2 1 1 0 0 1 0 |
3 1 |