L Tiling

Let $(r,c)$ denote the cell in the $r$-th row from the top and the $c$-th column from the left of an $N\times N$ grid.

An L tile of length $X$ consists of one center cell and $X$ cells extending in a straight line from the center in each of two mutually perpendicular directions. It has $2X+1$ cells in total and can be rotated freely. There is one tile of each length $1,2,\cdots,N-1$. Place all the tiles aligned with the grid. Tiles may not extend outside the board or overlap each other, and must be the only uncovered cell.

Find one possible placement, or determine that it is impossible.

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, if no placement exists, print -1 on a single line.

If a placement exists, print $N$ lines with $N$ integers each. The $j$-th integer on the $i$-th line is the length of the tile covering $(i,j)$. Print for .

• $1\leq T\leq100\,000$.
• $1\leq N\leq1000$.
• $1\leq R,C\leq N$.