Given a positive integer $n$, you need to construct an $n \times n$ matrix. The element in the $i$-th row and $j$-th column of the matrix is denoted as $A_{i,j}$. Your goal is to ensure that for all $1 \le i \le n$ and $1 \le j \le n$:

• If $i > 1$, then $\gcd(A_{i,j}, A_{i-1,j}) = 1$.
• If $j > 1$, then $\gcd(A_{i,j}, A_{i,j-1}) = 1$.

Furthermore, all numbers must satisfy $1 \le A_{i,j} \le n^2 + 40n$, and all numbers must be distinct. In other words, in the matrix, every number is coprime to its four neighbors (up, down, left, right), and no number in the matrix exceeds $n^2 + 40n$. $\gcd(x, y)$ denotes the greatest common divisor of $x$ and $y$.

Input

A single positive integer $n$ ($1 \le n \le 2500$).

Output

Output $n$ lines, each containing $n$ positive integers separated by spaces. If there are multiple valid solutions, output any one of them.

Examples

Input 1

2

Output 1

1 3
5 4

Input 2

3

Output 2

1 5 9
4 7 8
3 2 11

Note

The output size for this problem is large. Please add the following statements at the beginning of your program to disable input/output stream synchronization and speed up output:

ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);