Background

NOIP 1997 Senior, Problem 1.

P5512 is the enhanced testdata version of this problem.

The actual constraints for this problem are $1\le N\le 5$. There is no guarantee that a solution without hardcoding can pass the original constraints.

Problem Description

On an $N \times N$ ($1 \le N \le 10$) board, fill in the $N ^ 2$ numbers $1, 2, \dots, N ^ 2$, so that the sum of any two adjacent numbers is a prime number.

For example, when $N = 2$, there is:

The adjacent pairs whose sums are prime are:

$1+2,1+4,4+3,2+3$

When $N=4$, one possible arrangement is:

Here we stipulate that the top-left cell must contain the number $1$.

Input Format

A single integer $N$.

Output Format

If multiple solutions exist, output the arrangement whose sum of the first row and the first column is minimal. Output the board in $N$ lines, each containing $N$ integers separated by single spaces. If no solution exists, output NO.

1

NO

2

1 2
4 3

Hint

Translated by ChatGPT 5