Description

给定 $n$ 个长度为 $m$ 的二进制字符串 $s_1, s_2, \ldots, s_n$ ，每个字符串由字符 0 和 1 组成。存在一个神秘数字 $x$ （ $1 \leq x \leq m$ ），对于每个字符串 $s_i$ ，你可以得知 $s_i[x]$ 的值。

你的任务是确定至少需要添加多少个长度为 $m$ 的二进制字符串到现有集合中，使得通过查询所有字符串（包括添加的字符串）的 $s_i[x]$ 值，能够唯一确定神秘数字 $x$ 。

Input

第一行一个整数 $T$ （ $1 \leq T \leq 10^4$ ），表示测试数据的组数。

对于每组数据，第一行两个整数 $n$ 和 $m$ （ $1\le n,m\le 10^6,n \cdot m \leq 10^6$ ），分别表示二进制字符串的数量和每个字符串的长度。

接下来 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串 $s_i$ 。

保证所有数据的 $n \cdot m$ 之和不超过 $10^6$ 。

对于每组数据，输出一个整数，表示至少需要添加的二进制字符串的数量，以确保能够唯一确定神秘数字 $x$ 。

1
0

第一组样例中，我们可以添加字符串 $s_3=\texttt{001001}$ ，当我们询问得知 $s_1[x] = 0,s_2[x] = 0,s_3[x] =1$ 的时候我们可以确定 $x = 6$ 。当 $x$ 为其他值的时候也可以类似猜中。

The 23rd UESTC Programming Contest Preliminary