Henry Porter and the Palindromic Radius

A young wizard, Henry Porter, has just received sad news. His eldest relative, uncle Markus Radius Palindromus Black, has passed away. Uncle Markus was known as an eccentric person who used complicated binary magic, and he was also very, very rich.

Black's will states that Henry should inherit his mysterious chamber of treasures. To enter and claim it, however, the young wizard must say the right password $H$, a word of length $n$ consisting of characters 0 and 1. Uncle Markus did not tell Henry the password. Instead, for every $x = 1, 2, \ldots, n$, he computed the palindromic radius $p_x$, the largest integer such that the word $H[x - p_x .. x + p_x]$ of length $2p_x + 1$ centered at $H[x]$ exists and is a palindrome. Henry only received the values $p_1, \ldots, p_n$. For example, if the password was 10111010, Henry would get the sequence $(0, 1, 0, 3, 0, 1, 1, 0)$.

Henry would rather Uncle Markus not test his algorithmic skills from beyond the grave, but he has good friends who can help. Given the sequence left in the will, determine all possible passwords that match it. Since the will is battered and stained, it may happen that there is no solution at all.

The first line contains the number of test cases $z$ ($1 \le z \le 200000$). Each test case consists of two lines. The first line contains a single integer $n$, the length of both the password and Black's sequence ($2 \le n \le 1000000$). The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($0 \le p_i \le n$), the palindromic radii. The sum of $n$ over all test cases does not exceed $5 \times 10^7$.

For every test case, first output the number $k$ of possible passwords. If $k > 0$, output the $k$ passwords on the next $k$ lines as $\{0,1\}$-sequences in lexicographic order. You may assume that $k$ does not exceed 100.