这是问题的简单版本。在此版本中,$$$n$$$ 的上限以及所有测试用例的 $$$n$$$ 总和为 $$$2\,000$$$;此外,测试用例的最大数量为$$$200$$$。
存在大小为 $$$n$$$$$$^{\text{*}}$$$ 的排列 $$$p$$$。
它是通过通信通道发送的,如下所示:首先,排列中每个数字 $$$p_{i}$$$ 的所有 $$$0$$$ 位都作为 $$$n$$$ 字符的字符串发送 0 和/或 1;然后 $$$1$$$-st 位以相同的格式发送,依此类推,直到数字 $$$n$$$ 的最高有效位。
例如,对于 $$$p = [3, 1, 2, 4]$$$,发送了以下三个字符串:
- "1100";
- "1010";
- "0001".
您收到了所有这些字符串,但是每个字符串对应一位的顺序丢失了,即字符串以任意顺序到达。在上面的示例中,字符串可能按“1010", "0001“,和”1100".
您的任务是确定可以传输多少种可能的原始排列 $$$p$$$。有可能数据在传输过程中被损坏,然后就没有有效的原始排列$$$p$$$。
$$$^{\text{*}}$$$大小 $$$n$$$ 的排列是大小为 $$$n$$$ 的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - 问题的答案。
示例
输入复制
61141010000101107010101111001010110110510110011001100160010111110000000007110000111000011100011
输出复制
126000
注意
在第一个示例中,只能有一个排列,$$$p = [1]$$$。
在第二个示例中,有 $$$2$$$ 可能的变体:$$$[1, 2, 3, 4]$$$ 和 $$$[2, 1, 3, 4]$$$。
在第四个示例中,没有合适的原始排列。