P13007 【MX-X13-T2】「KDOI-12」不要去思考未来，把这留给未来的你。

未来的你在打一场模拟赛。

模拟赛中共有 $T$ 道题，每道题有 $n$ 个子任务和 $m$ 个特殊性质。每个子任务均满足 $m$ 个特殊性质的一个子集。 定义一组子任务依赖 $(i,j)$ 表示子任务 $j$ 依赖子任务 $i$，也就是只有通过了子任务 $i$ 才能通过子任务 $j$。 考虑到模拟赛有懒惰的出题人和愚蠢的在线法官，子任务依赖的条数必然是越少越好。现在你想知道最少配置多少组子任务依赖才能保证： * 不存在一对子任务 $x,y$ 使得满足子任务 $y$ 的数据必然满足子任务 $x$，但是在不通过子任务 $x$ 的情况下**仍然有可能**通过子任务 $y$； * 不存在一对子任务 $x,y$ 使得存在满足子任务 $y$ 的数据**不**满足子任务 $x$，但是在不通过子任务 $x$ 的情况下**无法**通过子任务 $y$。 形式化地讲，设第 $i$ 个子任务的特殊性质集合为 $S_i$，那么你要选择尽可能少的 $(u_x,v_x)$ 二元组使得： * 对于任意 $(i,j)$ 满足 $S_i\subseteq S_j$，均存在 $j=p_1,p_2,\dots,p_M=i$ 使得对于任意 $1\leq k

第一行，一个正整数 $T$，表示题目数量。对于每道题目： * 第一行，两个正整数 $n,m$，表示子任务数量和特殊性质数量。 * 接下来 $n$ 行，每行一个长度为 $m$ 的 `01` 串。第 $i$ 个子任务满足特殊性质 $j$ 当且仅当第 $i$ 行的字符串的第 $j$ 个字符为 `1`。 **保证不存在两个子任务满足的特殊性质相同。**

对于每道题目，一行，一个非负整数，表示子任务依赖数量的最小值。

**【样例解释】** 对于第二道题目：不妨设四个特殊性质分别为 $\text{ABCD}$，那么五个子任务分别符合特殊性质 $\{\text{ABC}\}$、$\{\text{AB}\}$、$\{\text{A}\}$、$\{\text{D}\}$、和 $\varnothing$。可以证明，配置以下子任务依赖符合要求且最优： * $(1,2)$； * $(2,3)$； * $(3,5)$； * $(4,5)$。 **【数据范围】** | 测试点编号 | $n,m\leq$ | 特殊性质 | |:--:|:--:|:--:| | $1\sim2$ | $2$ | 无 | | $3\sim9$ | $5$ | 无 | | $10\sim13$ | $10$ | 无 | | $14\sim20$ | $16$ | A | | $21\sim25$ | $16$ | 无 | * 特殊性质 A：保证每个子任务最多满足两个特殊性质。 对于所有数据：$1\leq T\leq 6$，$1\leq n,m\leq16$，输入的字符串由 `0` 和 `1` 组成，保证不存在两个子任务满足的特殊性质相同。