G. 分辨矩阵
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

有若干大小为 $$$n\times m$$$ 的01矩阵，它们互不相同，该如何区分呢？

聪明的你想到，其实不需要所有位置逐一比较，只需要选取一些特殊的位置就可以区分，这样大大减少了工作量。

举个栗子，下面有四个 $$$2\times 3$$$ 的01矩阵。我们只需要根据 $$$(0, 0)$$$ 和 $$$(0,1)$$$ 这两个位置即可将它们全部区分。

$$$$$$ \begin{bmatrix} 0 & 0 & 0\\ 1 & 1 & 1\\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 1\\ 1 & 1 & 0\\ \end{bmatrix} \begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix} \begin{bmatrix} 1 & 1 & 0\\ 0 & 1 & 1\\ \end{bmatrix} $$$$$$

于是问题来了，最少需要选取几个位置呢？相信聪明的你一定能解决。

Input

第一行一个正整数 $$$T(1\leq T\leq 50)$$$，表示数据组数。

接下来 $$$T$$$ 组数据，每组数据格式如下：

第一行三个整数 $$$n,m,k(1\leq n,m\leq 10,2\leq k\leq 6)$$$，表示01矩阵的大小，以及个数。

接下来 $$$k$$$ 个矩阵，每个矩阵 $$$n$$$ 行，每行一个长为 $$$m$$$ 的01串。

Output

输出 $$$T$$$ 行，每行一个正整数，表示答案。

Example
Input
1
3 6 3
111111
111111
110111
111110
110111
111111
111111
111111
111111
Output
2
Note

对于给出的样例，三个矩阵分别为： $$$$$$ \begin{bmatrix} 1&1&1&1&1&1\\ 1&1&1&1&1&1\\ 1&1&0&1&1&1\\ \end{bmatrix} \begin{bmatrix} 1&1&1&1&1&0\\ 1&1&0&1&1&1\\ 1&1&1&1&1&1\\ \end{bmatrix} \begin{bmatrix} 1&1&1&1&1&1\\ 1&1&1&1&1&1\\ 1&1&1&1&1&1\\ \end{bmatrix} $$$$$$

取 $$$(2,2),(1,2)$$$ 即可分辨这三个矩阵，因此答案为 $$$2$$$。