Light Up

Light Up is a puzzle played on a square board. Each cell of an $N \times N$ board is either a black square or a white square. The goal is to place light bulbs on some white squares so that every white square is lit.

A white square is lit when a bulb stands in the same row or the same column and no black square lies between them. A square that holds a bulb is lit as well. A bulb can be placed only on a white square.

Figure 1

Placing a bulb at $(3, 3)$ on the board of figure 1 gives the situation in figure 2.

Figure 2

Placing a bulb on a white square that is already lit overheats the bulb, so such a placement is not allowed. Bulbs at both $(2, 3)$ and $(3, 3)$, as in figure 3, are impossible.

Figure 3

Some black squares carry a digit. The digit is the number of squares that must hold a bulb among the squares sharing an edge with that black square. Look at the board in figure 4.

Figure 4

Figure 5 shows one placement that satisfies every rule on the board of figure 4.

Figure 5

Given a board, find a placement that solves the puzzle.

The first line holds the number of test cases $T$. ($1 \le T \le 30$)

The first line of each test case holds the board size $N$. ($1 \le N \le 7$)

Each of the next $N$ lines holds $N$ integers separated by a space. The $j$-th integer of the $i$-th line is the description $R_{ij}$ of the cell at $(i, j)$. A value of $-2$ means a white square, $-1$ means a black square with no digit, and a value from $0$ to $4$ means a black square carrying that digit.

For each test case print $N$ lines, each holding $N$ integers equal to $0$ or $1$ and separated by a space. Print $1$ for a cell that holds a bulb and $0$ for a cell that does not. Print the answers of the test cases in the order the boards are given.

Every input has at least one valid placement. When more than one placement satisfies the rules, print only the lexicographically smallest one. Read a placement from the first line to the last, and inside a line from left to right, as a sequence of $N \times N$ digits $0$ and $1$. The answer is the placement whose sequence is smallest in lexicographic order. In other words, walking the cells in that order, a cell holds $0$ whenever the puzzle can still be finished with $0$ in it.