如果数字 $$$a$$$ 和 $$$b$$$ 恰好相差一,即 $$$|a-b|=1$$$,我们将认为它们是相邻的。
如果方阵 $$$n \times n$$$ 有公共边,我们将认为它们是相邻的,也就是说,对于单元格 $$$(r, c)$$$,单元格 $$$(r, c-1)$$$、$$$(r, c+1)$$$、$$$(r-1, c)$$$ 和 $$$(r+1, c)$$$ 与其相邻。
对于给定的数字 $$$n$$$,构造一个方阵 $$$n \times n$$$ 使得:
- 从 $$$1$$$ 到 $$$n^2$$$ 的每个整数在此矩阵中只出现一次;
- 如果 $$$(r_1, c_1)$$$ 和 $$$(r_2, c_2)$$$ 是相邻单元格,则其中写入的数字不得相邻。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$)。然后是 $$$t$$$ 测试用例。
每个测试用例都由一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) 来表征。
输出
对于每个测试用例,输出:
- -1,如果所需矩阵不存在;
- 所需的矩阵,否则(任何此类矩阵,如果存在多个矩阵)。
矩阵应输出为 $$$n$$$ 行,其中每行包含 $$$n$$$ 整数。
示例
输入 #1
3 1 2 3
输出 #1
1 -1 2 9 7 4 6 3 1 8 5