The Rutgers scientific committee members don't like magic, and by extension, they don't like magic squares either. Thus, they like to construct grids of numbers that completely go against the principles of magic squares. Here is how they do it.
They start with an $$$n \times n$$$ grid of cells, and in each cell they put an integer from the range $$$[1, 4]$$$. The numbers are chosen such that the set formed by taking the $$$2n$$$ row and column sums consists of $$$2n$$$ distinct values (diagonal sums are not considered).
Given an integer $$$n$$$, your task is to construct an $$$n \times n$$$ grid according to the above rules. It can be proven that such a grid always exists.
The first line of the input contains a single integer $$$t$$$ ($$$1\le t\le 40$$$) — the number of test cases.
Each test case consists of a single line containing a single integer $$$n$$$ ($$$2\le n\le 1000$$$) — the side length of the grid.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.
For each test case, print $$$n$$$ lines containing $$$n$$$ characters each. Every character should be one of 1, 2, 3, or 4. The values obtained by summing along any row or column in the output should all be pairwise distinct.
If there are multiple solutions, print any.
224
12331312232324431211
For the first test case, the row sums are $$$3$$$ and $$$6$$$, and the column sums are $$$4$$$ and $$$5$$$. All four of these numbers are distinct.
The second test case corresponds to the image above.
