Prime Sum Chessboard

Given a chessboard of size \(N \times N\) (with \(1 \le N \le 10\)), fill the board with the numbers \(1, 2, \dots, N^2\) (each used exactly once) such that for every pair of adjacent cells (sharing a common edge) the sum of their numbers is a prime number. In addition, the cell at the top left corner (first row, first column) must contain the number \(1\).

Two cells are considered adjacent if they share a common edge (up, down, left, or right). Note that even though many sums of an odd and an even number are odd, not every odd number is prime. For example, when \(N=2\), one valid solution is:

In this case the sums of adjacent cells are \(1+2=3\), \(1+4=5\), \(4+3=7\), and \(2+3=5\) — all prime numbers.

For \(N=4\), one valid solution is:

Your task is to output any valid board configuration given \(N\). It is guaranteed that a solution exists for the test cases provided.

All sums in the conditions which involve numbers must be written using \(\LaTeX\) format when describing formulas. For example, write \(N^2\) and \(1+2=3\) in \(\LaTeX\) format.

inputFormat

The input consists of a single integer \(N\) on one line, where \(1 \le N \le 10\).

outputFormat

Output \(N\) lines, each containing \(N\) space-separated integers representing a valid filling of the chessboard. The top left cell must be \(1\). If multiple solutions exist, output any one of them.

sample

1

1