CF1734B.Bright, Nice, Brilliant

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 \lt 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.

存在一座由 $n$ 层组成的金字塔。各层从上到下按递增顺序编号。在该金字塔中，第 $i$ 层包含 $i$ 个房间。

记第 $i$ 层的第 $j$ 个房间为 $(i,j)$。对所有满足 $1 \le j \le i < n$ 的正整数 $i$ 和 $j$，均存在两条单向楼梯：一条从 $(i,j)$ 通向 $(i+1,j)$，另一条从 $(i,j)$ 通向 $(i+1,j+1)$。

每个房间中，你可以放置一支火把，也可以保持空置。定义房间 $(i, j)$ 的亮度为：所有能通过零次或多次楼梯到达房间 $(i, j)$ 的、放置了火把的房间的总数。

例如，当 $n=5$，且火把放置在房间 $(1,1)$、$(2,1)$、$(3,2)$、$(4,1)$、$(4,3)$ 和 $(5,3)$ 时，该金字塔可图示如下：

在上图中，放置火把的房间以黄色标出，空房间为白色。右下角的蓝色数字表示对应房间的亮度。

房间 $(4,2)$（带星号的房间）的亮度为 $3$。在下图中，所有能到达 $(4,2)$ 的房间以红色边框标出。由于这些房间中共有三支火把，因此其亮度为 $3$。

当且仅当每一层的所有房间亮度均相等时，该金字塔被称为优美的。

定义一座优美金字塔的辉光值为房间 $(1,1)$、$(2,1)$、$(3,1)$、…、$(n,1)$ 的亮度之和。

请给出一种火把布置方案，使得所得金字塔是优美的，且其辉光值最大。

可以证明，这样的方案一定存在。若存在多种方案，输出任意一种即可。

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$.

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅一行，包含一个正整数 $n$（$1 \le n \le 500$），表示金字塔的层数。

保证所有测试用例的 $n$ 值之和不超过 $500$。

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.

对于每个测试用例，输出 $n$ 行，表示金字塔中火把的排列方式。

第 $i$ 行应包含 $i$ 个整数，各整数之间以空格分隔。第 $i$ 行的第 $j$ 个整数应为 $1$（若房间 $(i,j)$ 中有火把），否则为 $0$。

可以证明答案总是存在的。若存在多个答案，输出任意一个即可。

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.

在第三个测试用例中，火把放置在 $(1,1)$、$(2,1)$、$(2,2)$、$(3,1)$ 和 $(3,3)$ 处。

该金字塔是“优美的”，因为每一层的房间具有相同的亮度。例如，第三层的所有房间亮度均为 $3$。

该金字塔的“辉煌值”为 $1+2+3 = 6$。可以证明：当 $n=3$ 时，不存在辉煌值更大的布置方案。