← 返回题目列表

Codeforces · 2081/F

F. 热门矩阵

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

小猪周喜欢矩阵,尤其是那些让他兴奋的矩阵,叫做 热门矩阵.

大小为 $$$n \times n$$$ 的热矩阵可以定义如下。令 $$$a_{i, j}$$$ 表示第 $$$i$$$ 行、第 $$$j$$$ 列中的元素 ($$$1 \le i, j \le n$$$)。

  1. 矩阵的每一列和行都是从 $$$0$$$ 到 $$$n-1$$$ 的所有数字的排列。
  2. 对于每对索引 $$$i$$$, $$$j$$$,使得 $$$1 \le i, j \le n$$$, $$$a_{i, j} + a_{i, n - j + 1} = n - 1$$$。
  3. 对于每对索引 $$$i$$$, $$$j$$$,使得 $$$1 \le i, j \le n$$$, $$$a_{i, j} + a_{n - i + 1, j} = n - 1$$$。
  4. 所有有序对 $$$\left(a_{i, j}, a_{i, j + 1}\right)$$$,其中 $$$1 \le i \le n$$$、$$$1 \le j \lt n$$$ 都是不同的。
  5. 所有有序对 $$$\left(a_{i, j}, a_{i + 1, j}\right)$$$,其中 $$$1 \le i \lt n$$$、$$$1 \le j \le n$$$ 都是不同的。

现在,小猪周给了你一个数字$$$n$$$,如果给定的$$$n$$$存在热矩阵,你需要为他提供一个热矩阵,或者告诉他,如果给定的$$$n$$$不存在热矩阵,他永远不会兴奋。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3000$$$)。

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

输出

对于每个测试用例,打印“NO"(不带引号)如果给定的 $$$n$$$ 不存在热矩阵。

否则,打印“是"(不带引号)在第一行。然后输出$$$n$$$行,每行有$$$n$$$个数字,代表满足问题要求的大小为$$$n\times n$$$的热矩阵。

如果有多个解决方案,请打印其中任何一个。

示例

输入
复制

4
1
2
3
4

输出
复制

YES
0
YES
0 1
1 0
NO
YES
0 1 2 3
1 3 0 2
2 0 3 1
3 2 1 0

注意

在第一个、第二个和第四个测试用例中,可以验证示例中提供的矩阵满足问题中陈述的所有条件。

在第三个测试用例中,通过枚举所有可能的矩阵,可以证明不存在满足问题条件的热矩阵。