Bright, Nice, Brilliant
Contest: Codeforces Round 822 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms

There is a pyramid which consists of $$$n$$$ floors. The floors are numbered from top to bottom in increasing order. In the pyramid, the $$$i$$$-th floor consists of $$$i$$$ rooms.

Denote the $$$j$$$-th room on the $$$i$$$-th floor as $$$(i,j)$$$. For all positive integers $$$i$$$ and $$$j$$$ such that $$$1 \le j \le i < n$$$, there are $$$2$$$ one-way staircases which lead from $$$(i,j)$$$ to $$$(i+1,j)$$$ and from $$$(i,j)$$$ to $$$(i+1,j+1)$$$ respectively.

In each room you can either put a torch or leave it empty. Define the brightness of a room $$$(i, j)$$$ to be the number of rooms with a torch from which you can reach the room $$$(i, j)$$$ through a non-negative number of staircases.

For example, when $$$n=5$$$ and torches are placed in the rooms $$$(1,1)$$$, $$$(2,1)$$$, $$$(3,2)$$$, $$$(4,1)$$$, $$$(4,3)$$$, and $$$(5,3)$$$, the pyramid can be illustrated as follows:

In the above picture, rooms with torches are colored in yellow, and empty rooms are white. The blue numbers in the bottom-right corner indicate the brightness of the rooms.

The room $$$(4,2)$$$ (the room with a star) has brightness $$$3$$$. In the picture below, the rooms from where you can reach $$$(4,2)$$$ have red border. The brightness is $$$3$$$ since there are three torches among these rooms.

The pyramid is called nice if and only if for all floors, all rooms in the floor have the same brightness.

Define the brilliance of a nice pyramid to be the sum of brightness over the rooms $$$(1,1)$$$, $$$(2,1)$$$, $$$(3,1)$$$, ..., $$$(n,1)$$$.

Find an arrangement of torches in the pyramid, such that the resulting pyramid is nice and its brilliance is maximized.

We can show that an answer always exists. If there are multiple answers, output any one of them.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single positive integer $$$n$$$ ($$$1 \le n \le 500$$$) — the number of floors in the pyramid.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

Output format:
For each test case, output $$$n$$$ lines, the arrangement of torches in the pyramid.

The $$$i$$$-th line should contain $$$i$$$ integers, each separated with a space. The $$$j$$$-th integer on the $$$i$$$-th line should be $$$1$$$ if room $$$(i,j)$$$ has a torch, and $$$0$$$ otherwise.

We can show that an answer always exists. If there are multiple answers, output any one of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the third test case, torches are placed in $$$(1,1)$$$, $$$(2,1)$$$, $$$(2,2)$$$, $$$(3,1)$$$, and $$$(3,3)$$$.

The pyramid is nice as rooms on each floor have the same brightness. For example, all rooms on the third floor have brightness $$$3$$$.

The brilliance of the pyramid is $$$1+2+3 = 6$$$. It can be shown that no arrangements with $$$n=3$$$ will have a greater brilliance.

Example input:
3
1
2
3

Example output:
1 
1 
1 1 
1 
1 1 
1 0 1

Editorial:
Note that the brightnesses of the rooms on the $$$i$$$-th floor is at most $$$i$$$. This is because in room $$$(i,1)$$$, only $$$i$$$ rooms, namely, $$$(1,1)$$$, $$$(2,1)$$$, $$$\ldots$$$, $$$(i,1)$$$ can reach to $$$(i,1)$$$ through some number of staircases.
It is also possible to find a configuration of torches in the pyramid such that the brightnesses of the rooms on the $$$i$$$-th floor is exactly $$$i$$$, i.e. it attains the upper bound.
The configuration is as follows: Room $$$(i,j)$$$ contains a torch if and only if it is the leftmost room ($$$i=1$$$) or the rightmost room ($$$i=j$$$) on the $$$i$$$-th floor.
This is valid because for all rooms $$$(i,j)$$$, it can be reached from $$$(1,1)$$$, $$$(2,1)$$$, $$$(3,1)$$$, $$$\ldots$$$, $$$(i-j+1,1)$$$ and $$$(2,2)$$$, $$$(3,3)$$$, $$$\ldots$$$, $$$(j,j)$$$. In other words, room $$$(i,j)$$$ has brightness $$$(i-j+1)+j-1=i$$$, so the pyramid is nice.