Description

The mock contest consists of $T$ problems. Each problem has $n$ subtasks and $m$ special properties. Each subtask satisfies a subset of the $m$ special properties.

A subtask dependency $(i,j)$ means that subtask $j$ depends on subtask $i$—that is, subtask $j$ can only be passed after subtask $i$ is passed.

Considering that the problem setters are lazy and the online judge is "not very smart," the number of subtask dependencies should be minimized. Now, you need to determine the minimum number of subtask dependencies required to ensure:

1. There does not exist a pair of subtasks $(x, y)$ such that:

   • All test cases satisfying subtask $y$ must also satisfy subtask $x$, but
   • It is still possible to pass subtask $y$ without passing subtask $x$.

2. There does not exist a pair of subtasks $(x, y)$ such that:

   • There exists a test case satisfying subtask $y$ but not satisfying subtask $x$, but
   • It is impossible to pass subtask $y$ without passing subtask $x$.

Formally, let $S_i$ denote the set of special properties satisfied by subtask $i$. You need to select the smallest possible number of $(u_x, v_x)$ pairs such that:

• For any $(i,j)$ where $S_i \subseteq S_j$, there exists a sequence $j = p_1, p_2, \dots, p_m = i$ such that for all $1 \leq k < m$, there exists $x$ where $(u_x, v_x) = (p_k, p_{k+1})$.
• For any $(i,j)$ where $S_i \not\subseteq S_j$, there does not exist any sequence $j = p_1, p_2, \dots, p_m = i$ such that for all $1 \leq k < m$, there exists $x$ where $(u_x, v_x) = (p_k, p_{k+1})$.

Your task is to find the minimum number of such pairs.

Input Format

• The first line contains a positive integer $T$, the number of problems.
• For each problem:
  • The first line contains two positive integers $n$ and $m$, the number of subtasks and special properties, respectively.
  • The next $n$ lines each contain a binary string of length $m$. The $j$-th character of the $i$-th string is 1 if and only if the $i$-th subtask satisfies the $j$-th special property.
  • It is guaranteed that no two subtasks satisfy the exact same set of special properties.

Output Format

For each problem, output a single non-negative integer—the minimum number of subtask dependencies required.

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

Hint

Sample Explanation

For the second problem: Suppose the four special properties are $\text{ABCD}$. Then, the five subtasks correspond to the following sets:

• $\{\text{A}, \text{B}, \text{C}\}$
• $\{\text{A}, \text{B}\}$
• $\{\text{A}\}$
• $\{\text{D}\}$
• $\varnothing$ (empty set)

The following dependency configuration is optimal:

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

Data Range

• Special Property A: Each subtask satisfies at most two special properties.

For all test cases:

• $1 \leq T \leq 6$,
• $1 \leq n, m \leq 16$,
• Input strings consist of 0 and 1,
• No two subtasks share the exact same set of special properties.

Translated by DeepSeek V3.