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.

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.

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