CF2233E2.Permutation Transmission (Difficult Version)

This is the difficult version of the problem. In this version, the upper bound on $n$ and the sum of $n$ over all test cases is $2 \cdot 10^5$; furthermore, the maximum number of test cases is $10^4$.

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 \cdot 10^5$；此外，测试用例的最大数量为 $10^4$。

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

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

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

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

你接收到了所有这些字符串，但丢失了每个字符串所对应的位位置（即第 $0$ 位、第 $1$ 位等）信息——换言之，这些字符串以任意顺序到达。在上面的例子中，接收到的字符串顺序可能为 "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 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).

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 \cdot 10^{5}$.

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

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

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

附加输入约束：

• 所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^{5}$。

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]$。

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