年轻的巫师哈利·波特刚刚收到一个悲伤的消息——他家族中最年长的成员，马库斯·半径·回文·布莱克（Markus Radius Palindromus Black）叔叔去世了。马库斯叔叔以古怪著称，擅长复杂的二进制魔法，而且众所周知，他非常、非常有钱。

布莱克的遗嘱中写道，哈利将继承他神秘的宝藏室。然而，为了进入并领取宝藏，这位年轻的巫师必须说出正确的密码 $H$。这是一个长度为 $n$ 的字符串，由字符 '0' 和 '1' 组成。马库斯叔叔并没有直接告诉哈利密码——这显然不符合他的风格。相反，他计算了对于每个 $x = 1, 2, \dots, n$ 的回文半径 $p_x$——即满足以 $H[x]$ 为中心、长度为 $2p_x + 1$ 的子串 $H[x - p_x \dots x + p_x]$ 为回文串的最大整数 $p_x$。哈利最终只收到了这些数值 $p_1, \dots, p_n$。例如，如果密码是 10111010，哈利得到的序列将是 $(0, 1, 0, 3, 0, 1, 1, 0)$。

哈利宁愿马库斯叔叔不要在他死后还测试他的算法能力，但没办法，没有人可以抱怨。好在他有可以帮忙的好朋友！给定马库斯在遗嘱中留下的序列，请确定所有符合该序列的可能密码。由于遗嘱破损且污损，甚至可能根本不存在任何解。

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 200\,000$)。接下来是各个测试用例，每个测试用例的格式如下：

每个测试用例包含两行。第一行包含一个整数 $n$——密码和布莱克序列的长度 ($2 \le n \le 1\,000\,000$)。第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($0 \le p_i \le n$)——密码中所有字符的回文半径。

所有测试用例的 $n$ 之和不超过 $5 \cdot 10^7$。

输出格式

对于每个测试用例，首先输出可能的密码数量 $k$。如果 $k > 0$，则在接下来的 $k$ 行中输出所有解，即由 '0' 和 '1' 组成的序列。序列必须按字典序输出。

你可以假设 $k$ 不超过 $100$。

样例

输入 1

1
8
0 1 0 3 0 1 1 0

输出 1

4
00010000
01000101
10111010
11101111