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:

"1100";
"1010";
"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.

Input

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}$$$.

Output

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

Note

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.

Permutation Transmission (Difficult Version)

Examples