CF2233E1.Permutation Transmission (Easy Version)

This is the easy version of the problem. In this version, the upper bound on $n$ and the sum of $n$ over all test cases is $2\,000$; furthermore, the maximum number of test cases is $200$.

There was a permutation $p$ of size $n$$^{\text{∗}}$.

It was sent through a communication channel as follows: first, all $0$-th bits of each number $p_{i}$ in the permutation were sent as one string of $n$ characters 0 and/or 1; then the $1$-st bits were sent in the same format, and so on, up to the most significant bit of the number $n$.

For example, for $p = [3, 1, 2, 4]$, the following three strings were sent:

1. "1100";
2. "1010";
3. "0001".

You received all these strings, but the order in which each string corresponded to a bit was lost, that is, the strings arrived in arbitrary order. In the example above, the strings could have arrived in the order "1010", "0001", and "1100".

Your task is to determine how many possible original permutations $p$ could have been transmitted. It is possible that the data was corrupted during transmission, and then there is no valid original permutation $p$.

$^{\text{∗}}$A permutation of size $n$ is an array of size $n$ where each integer from $1$ to $n$ appears exactly once.

这是该问题的简单版本。在此版本中，$n$ 的上界以及所有测试用例中 $n$ 的总和为 $2\,000$；此外，测试用例的最大数量为 $200$。

存在一个长度为 $n$$^{\text{∗}}$ 的排列 $p$。

它通过通信信道以如下方式发送：首先，将排列中每个数 $p_{i}$ 的所有第 $0$ 位（最低位）作为一串长度为 $n$ 的由字符 0 和/或 1 组成的字符串发送；接着以相同格式发送所有第 $1$ 位，依此类推，直至数字 $n$ 的最高有效位为止。

例如，对于 $p = [3, 1, 2, 4]$，共发送了以下三个字符串：

1. "1100"；
2. "1010"；
3. "0001"。

你接收到了所有这些字符串，但丢失了每个字符串所对应的比特位编号（即字符串到达的顺序是任意的）。在上述例子中，字符串可能以 "1010"、"0001"、"1100" 的顺序到达。

你的任务是确定有多少种可能的原始排列 $p$ 可能被传输。传输过程中数据可能已损坏，此时不存在任何合法的原始排列 $p$。

$^{\text{∗}}$ 长度为 $n$ 的排列是指一个长度为 $n$ 的数组，其中 $1$ 到 $n$ 的每个整数恰好出现一次。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 200$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 2\,000$).

The next $\lceil\log_2 (n + 1) \rceil$ lines of each test case contain the transmitted data in the received order. Each line consists of $n$ characters $0$ and/or $1$.

Additional input constraints:

• the sum of $n$ over all test cases does not exceed $2\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 200$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\,000$）。

每个测试用例的接下来 $\lceil\log_2 (n + 1) \rceil$ 行按接收顺序包含传输的数据。每行由 $n$ 个字符组成，每个字符为 $0$ 或 $1$。

附加输入约束：

• 所有测试用例的 $n$ 值之和不超过 $2\,000$。

For each test case, print one integer — the answer to the problem.

对于每个测试用例，输出一个整数——即该问题的答案。

In the first example, there could be only one permutation, $p = [1]$.

In the second example, there are $2$ possible variants: $[1, 2, 3, 4]$ and $[2, 1, 3, 4]$.

In the fourth example, there are no suitable original permutations.

在第一个例子中，只可能存在一种排列：$p = [1]$。

在第二个例子中，存在 $2$ 种可能的排列：$[1, 2, 3, 4]$ 和 $[2, 1, 3, 4]$。

在第四个例子中，不存在满足条件的原始排列。