题目描述

这是本题的简单版。本版本中，$n$ 及所有测试组 $n$ 的总和上限均为 $2000$，测试组数上限为 $200$。

原本有一个大小为 $n$ 的排列 $p$。发送时，先把每个 $p_i$ 的第 $0$ 位组成一个长度为 $n$ 的 01 串发送，再发送第 $1$ 位，依此类推，直到 $n$ 的最高有效位。

例如 $p=[3,1,2,4]$ 时，会发送三个串：1100、1010、0001。

你收到了这些字符串，但它们对应哪一位的信息已经丢失，也就是这些字符串的顺序被任意打乱。请判断可能的原排列 $p$ 有多少个。如果数据已经损坏，可能不存在合法排列。

输入格式

第一行包含整数 $t$，表示测试组数。

每组测试数据第一行包含整数 $n$。

接下来 $\lceil\log_2(n+1)\rceil$ 行，每行是一个长度为 $n$ 的 01 串，表示收到的数据。

输出格式

对每组测试数据，输出一个整数，表示可能的原排列数量。

数据范围

• $1 \le t \le 200$
• $1 \le n \le 2000$
• 所有测试组的 $n$ 之和不超过 $2000$

2
1
1
2
10
01

1
2

提示

在第一个示例中，仅存在一种排列：$p = [1]$。

在第二个示例中，存在 $2$ 种可能情况：$[1, 2, 3, 4]$ 和 $[2, 1, 3, 4]$。

在第四个示例中，不存在符合条件的原始排列。

来源

Codeforces Round 2233 E1 - Permutation Transmission (Easy Version)