P12810 [AMPPZ 2019] Henry Porter and the Palindromic Radius

Source: [AMPPZ 2019](https://amppz.tcs.uj.edu.pl/2019/data.html).

年轻的巫师 Henry Porter 刚刚收到一个悲伤的消息——他家族中最年长的长辈，Markus Radius Palindromus Black 叔叔去世了。Black 叔叔以性格古怪著称，擅长复杂的二进制魔法，同时也以极其富有闻名。 Black 的遗嘱声明，Henry 将继承他神秘的宝藏密室。然而，要进入并认领宝藏，这位年轻巫师必须说出正确的密码 $H$——这是一个长度为 $n$、由字符 0 和 1 组成的单词。Black 叔叔并未直接告诉 Henry 密码（这显然不符合他的风格），而是为每个位置 $x = 1, 2, \ldots, n$ 计算了**回文半径** $p_x$——最大的整数，使得以 $H[x]$ 为中心、长度为 $2p_x + 1$ 的子串 $H[x - p_x \ldots x + p_x]$ 存在且为回文。Henry 只收到了这些值 $p_1, \ldots, p_n$。例如，如果密码是 `10111010`，Henry 会得到序列 $(0, 1, 0, 3, 0, 1, 1, 0)$。 Henry 希望 Black 叔叔别在死后还要考验他的算法能力，但抱怨也无济于事。好在他有能帮忙的朋友！根据遗嘱中留下的序列，确定所有可能的对应密码。由于遗嘱破损且污迹斑斑，甚至可能根本无解。

**本题单个测试点内有多组测试数据。** 输入的第一行包含测试数据数量 $z$（$1 \le z \le 200\,000$）。每组测试数据的格式如下： 每组测试数据包含两行。第一行包含一个整数 $n$——密码和 Black 序列的长度（$2 \le n \le 1\,000\,000$）。第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$0 \le p_i < n$）——密码中每个字符对应的回文半径。 所有测试数据的 $n$ 值总和不超过 $5 \cdot 10^7$。

对于每组测试数据，首先输出可能密码的数量 $k$。 如果 $k > 0$，则在接下来的 $k$ 行中按**字典序**输出所有可能的 $\{0, 1\}$ 序列形式的解。 可以假设 $k$ 不超过 100。