题目背景

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

题目描述

模拟赛中共有 $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<M$，存在 $x$ 使得 $u_x=p_k,v_x=p_{k+1}$；
• 对于任意 $(i,j)$ 不满足 $S_i\subseteq S_j$，均不存在 $j=p_1,p_2,\dots,p_M=i$ 使得对于任意 $1\leq k<M$，存在 $x$ 使得 $u_x=p_k,v_x=p_{k+1}$。

并求出选择二元组数量的最小值。

输入格式

第一行，一个正整数 $T$，表示题目数量。对于每道题目：

• 第一行，两个正整数 $n,m$，表示子任务数量和特殊性质数量。
• 接下来 $n$ 行，每行一个长度为 $m$ 的 01 串。第 $i$ 个子任务满足特殊性质 $j$ 当且仅当第 $i$ 行的字符串的第 $j$ 个字符为 1。

保证不存在两个子任务满足的特殊性质相同。

输出格式

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

3
4 2
00
01
10
11
5 4
1110
1100
1000
0001
0000
7 4
0101
1101
1001
0010
1110
0100
1000

4
4
7

提示

【样例解释】

对于第二道题目：不妨设四个特殊性质分别为 $\text{ABCD}$，那么五个子任务分别符合特殊性质 $\{\text{ABC}\}$、$\{\text{AB}\}$、$\{\text{A}\}$、$\{\text{D}\}$、和 $\varnothing$。可以证明，配置以下子任务依赖符合要求且最优：

• $(1,2)$；
• $(2,3)$；
• $(3,5)$；
• $(4,5)$。

【数据范围】

• 特殊性质 A：保证每个子任务最多满足两个特殊性质。

对于所有数据：$1\leq T\leq 6$，$1\leq n,m\leq16$，输入的字符串由 0 和 1 组成，保证不存在两个子任务满足的特殊性质相同。