有一个金字塔,由 $$$n$$$ 层组成。楼层从上到下按递增顺序编号。在金字塔中,$$$i$$$层由$$$i$$$个房间组成。
将 $$$i$$$ 层的第 $$$j$$$ 个房间表示为 $$$(i,j)$$$。对于所有正整数 $$$i$$$ 和 $$$j$$$ 使得 $$$1 \le j \le i < n$$$,存在 $$$2$$$ 单向楼梯,分别从 $$$(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)$$$ 的亮度总和。
在金字塔中找到火把的排列方式,这样最终的金字塔就很漂亮并且它的光彩最大化。
我们可以证明答案总是存在的。如果有多个答案,则输出其中任意一个。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含一个正整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 金字塔的楼层数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$。
输出
对于每个测试用例,输出 $$$n$$$ 行,即金字塔中火把的排列。
第 $$$i$$$ 行应包含 $$$i$$$ 个整数,每个整数之间用空格分隔。如果房间 $$$(i,j)$$$ 有火炬,则第 $$$i$$$ 行上的第 $$$j$$$ 整数应为 $$$1$$$,否则为 $$$0$$$。
我们可以证明答案总是存在的。如果有多个答案,则输出其中任意一个。
示例
输入 #1
3 1 2 3
输出 #1
1 1 1 1 1 1 1 1 0 1
注意
在第三个测试用例中,火把放置在 $$$(1,1)$$$、$$$(2,1)$$$、$$$(2,2)$$$、$$$(3,1)$$$ 和 $$$(3,3)$$$ 中。
金字塔很漂亮,因为每层的房间都有相同的亮度。例如,三楼的所有房间的亮度为$$$3$$$。
金字塔的光辉是$$$1+2+3 = 6$$$。可以证明$$$n=3$$$的安排不会有更大的辉煌。