Background

An enhanced testdata version of P1549.

The testdata has been expanded from 5 to 10.

Because the testdata for this problem may have many disputes, a separate problem is created to test the enhanced version testdata.

Problem Description

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

For example, when $N = 2$, one solution is:

The adjacent pairs whose sums are prime are:

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

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

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

Input Format

One line with an integer $N$.

Output Format

If there are multiple solutions, output the arrangement with the smallest sum of the first row and the first column. If there is no solution, output NO.

2

1 2
4 3

1

NO

Hint

$N\leq10$

For $N=1,2,\dots,10$, each has one test point. For some reasons, $N$ is not necessarily the same as the test point ID.

The testdata was newly fixed on 2020.1.20.

Translated by ChatGPT 5