您将获得 $$$n^2$$$ 卡,其价值从 $$$0$$$ 到 $$$n^2-1$$$。你要把它们按 $$$n$$$ 排列在 $$$n$$$ 网格中,这样就有 正是 每个单元格中有一张卡片。
子网格$$$^{\text{*}}$$$ 的 MEX(最小排除值)定义为子网格中未出现的最小非负整数。
您的任务是排列卡片,使所有 $$$\left(\frac{n(n+1)}{2}\right)^2$$$ 子网格的 MEX 值总和最大化。
$$$^{\text{*}}$$$$$$n$$$ 由 $$$n$$$ 网格组成的子网格由四个数字 $$$l_1, r_1, l_2, r_2$$$ 指定,满足 $$$1\le l_1\le r_1\le n$$$ 和 $$$1\le l_2\le r_2\le n$$$。当且仅当 $$$l_1\le i\le r_1$$$ 和 $$$l_2\le j\le r_2$$$ 时,网格的第 $$$i$$$ 行和第 $$$j$$$ 列中的元素是子网格的一部分。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 500$$$) — 网格的边长。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,输出 $$$n$$$ 行,每行包含代表网格元素的 $$$n$$$ 整数。
如果有多个答案,则可以输出其中任何一个。
示例
输入复制
223
输出复制
0 1 2 3 8 4 5 6 0 1 7 2 3
注意
在第一个测试用例中,一个有效的安排是:
| 0 | 1 |
| 2 | 3 |
总共有 $$$9$$$ 个子网格,其中 MEX 非零的 $$$4$$$ 如下所示:
| 0 |
| 0 | 1 |
| 0 |
| 2 |
| 0 | 1 |
| 2 | 3 |
所有子网格的 MEX 总和将为 $$$1+2+1+4 = 8$$$。可以证明没有其他安排具有更大的 MEX 值总和。