← 返回题目列表

Codeforces · 2101/A

A. 网格中的墨西哥人

中文机器翻译题面 查看原题

您将获得 $$$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$$$ 整数。

如果有多个答案,则可以输出其中任何一个。

示例

输入
复制

2
2
3

输出
复制

0 1 
2 3 
8 4 5 
6 0 1 
7 2 3

注意

在第一个测试用例中,一个有效的安排是:

01
23

总共有 $$$9$$$ 个子网格,其中 MEX 非零的 $$$4$$$ 如下所示:

0
值:$$$[0]$$$ — 墨西哥: $$$1$$$

01
值:$$$[0, 1]$$$  — 墨西哥: $$$2$$$

0
2
值:$$$[0, 2]$$$  — 墨西哥: $$$1$$$

01
23
值:$$$[0, 1, 2, 3]$$$  — 墨西哥: $$$4$$$

所有子网格的 MEX 总和将为 $$$1+2+1+4 = 8$$$。可以证明没有其他安排具有更大的 MEX 值总和。