题目描述

给定一个正整数 $N$。

请在一个 $N$ 行 $N$ 列的网格的每个格子中，各填入一个不超过 $N^2$ 的正整数，使得以下所有条件都成立：

• 任意两个在上下左右四个方向上相邻的格子中所填的正整数之和，都不是素数。
• 所有不超过 $N^2$ 的正整数恰好各出现一次。

在本题的限制条件下，可以证明一定存在一种满足条件的填法。

输入格式

输入从标准输入中按以下格式给出。

$N$

输出格式

请输出一种满足条件的填法。设 $A_{ij}$ 表示第 $i$ 行第 $j$ 列所填的正整数，输出格式如下：

$A_{11}$ $A_{12}$ $\ldots$ $A_{1N}$
$A_{21}$ $A_{22}$ $\ldots$ $A_{2N}$
$\vdots$
$A_{N1}$ $A_{N2}$ $\ldots$ $A_{NN}$

如果存在多种满足条件的填法，输出任意一种均可。

样例 1

输入

4

输出

15 11 16 12
13 3 6 9
14 7 8 1
4 2 10 5

说明/提示

限制

• $3 \leq N \leq 1000$

样例解释 1

在这个网格中，$1$ 到 $16$ 的所有正整数各出现了一次。相邻两个格子的数字之和如 $15+11=26$、$11+16=27$、$15+13=28$ 等，均不是素数。

由 ChatGPT 4.1 翻译