题目背景

Source: AMPPZ 2019.

题目描述

年轻的巫师 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。

1
8
0 1 0 3 0 1 1 0

4
00010000
01000101
10111010
11101111