存在一个大小为 n 的排列 p。

它通过通信通道发送如下：首先，排列中每个数字 p_i 的所有 0-th 位作为一个字符 0 和/或 1 的 n 字符串发送；然后以相同的格式发送 1-st 位，以此类推，直到数字 n 的最高有效位。

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

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

您收到了所有这些字符串，但是每个字符串对应于位的顺序丢失了，也就是说，字符串以任意顺序到达。在上面的示例中，字符串可能以 "1010"、"0001" 和 "1100" 的顺序到达。

你的任务是确定有多少可能的原始排列 p 可能被传输。有可能数据在传输过程中被损坏，因此没有有效的原始排列 p。

^{\text{∗}} 一个大小为 n 的排列是一个大小为 n 的数组，其中从 1 到 n 的每个整数只出现一次。

第一行包含一个整数 T（1 \le T \le 10^4），表示测试用例的数量。

每个测试用例的第一行包含一个整数 n（1 \le n \le 2 \cdot 10^5）。

接下来 n 行，每行包含一个长度为 n 的二进制字符串 s_i，表示接收到的第 i 个位平面。

保证所有测试用例的 n 之和不超过 2 \cdot 10^5。

对于每个测试用例，输出一个整数，表示可能的原始排列 p 的数量。

如果数据被损坏，没有有效的原始排列，则输出 0。

接收到的三个字符串分别是：

• "1100"
• "1010"
• "0001"

它们对应于三个位平面，但顺序未知。

唯一可能的原始排列是 p = [3, 1, 2, 4]，对应位平面为：

• 第 0 位：[1, 1, 0, 0] → "1100"
• 第 1 位：[1, 0, 1, 0] → "1010"
• 第 2 位：[0, 0, 0, 1] → "0001"

所以可能的排列数量为 1。