题目描述

这是本题的困难版。本版本中，$n$ 及所有测试组 $n$ 的总和上限均为 $2\cdot 10^5$，测试组数上限为 $10^4$。

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

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

输入格式

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

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

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

输出格式

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

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 2\cdot 10^5$
• 所有测试组的 $n$ 之和不超过 $2\cdot 10^5$

样例 1 输入

2
1
1
2
10
01

样例 1 输出

1
2

提示

在第一个示例中，可能只有一种排列，$p = [1]$。

在第二个示例中，有 $2$ 种可能的变体：$[1, 2, 3, 4]$ 和 $[2, 1, 3, 4]$。

在第四个示例中，没有合适的原始排列。

来源

Codeforces Round 2233 E2 - Permutation Transmission (Difficult Version)