Prime Adjacent Sums

Given an \(N \times N\) board (with \(1 \le N \le 10\)), fill the board with the numbers \(1, 2, \dots, N^2\) (each exactly once) so that for any two adjacent cells (sharing a common side) the sum of the numbers is a prime number. It is guaranteed that the cell in the top‐left corner contains the number \(1\).

For example, when \(N = 2\), one valid solution is:

The adjacent sums in this case are: \(1+2,\; 1+4,\; 4+3,\; 2+3\), each of which is prime.

Another example when \(N = 4\) is:

Your task is to produce one valid arrangement for the given \(N\). If multiple solutions exist, output any one of them.

inputFormat

The input consists of a single line containing an integer \(N\) (\(1 \le N \le 10\)).

outputFormat

Output the board as \(N\) lines, each containing \(N\) space-separated integers. The output must be a valid arrangement meeting the condition that for any two adjacent cells (up, down, left, right), the sum of their numbers is prime. The top left cell must contain \(1\).

sample

1

1