题目描述

有一个由 $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)$、$\ldots$、$(n,1)$ 这些房间亮度之和。

请你安排火把在金字塔中的放置方式，使得金字塔优美且辉煌度最大。

可以证明一定存在解。如果有多种方案，输出任意一种即可。

输入格式

输入的第一行为一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是每个测试用例的描述。

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

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

输出格式

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

第 $i$ 行包含 $i$ 个整数，空格分隔。第 $i$ 行第 $j$ 个整数为 $1$ 表示 $(i,j)$ 房间放有火把，为 $0$ 表示为空。

可以证明一定存在解。如果有多种方案，输出任意一种即可。

说明/提示

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

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

该金字塔的辉煌度为 $1+2+3=6$。可以证明，对于 $n=3$，不存在辉煌度更高的方案。

由 ChatGPT 4.1 翻译

样例

3
1
2
3

1 
1 
1 1 
1 
1 1 
1 0 1