G. 矩阵
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个正整数 $$$n$$$，你需要构造一个 $$$n\times n$$$ 的矩阵。

矩阵的第 $$$i$$$ 行第 $$$j$$$ 个元素，记作$$$A_{i,j}$$$。

你的目标是使得： 对于所有 $$$1 \leq i \leq n$$$ 且 $$$1 \leq j \leq n$$$，都有

  • 如果 $$$i \gt 1$$$，有 $$$ \gcd(A_{i,j}, A_{i-1,j}) = 1。$$$
  • 如果 $$$j \gt 1$$$，有 $$$ \gcd(A_{i,j}, A_{i,j-1}) = 1。$$$

并且所有的数字都满足 $$$ 1 \le A_{i,j} \le n^2 + 40 n $$$，且所有数字互不相同。

也就是说，矩阵中，所有的数字与它上下左右相邻的四个数字都互质，并且矩阵中的数都不超过 $$$n^2 + 40n$$$。

$$$\gcd(x,y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最大公约数。

Input

一行一个正整数 $$$n(1 \le n \le 2500)$$$。

Output

输出 $$$n$$$ 行，每行 $$$n$$$ 个正整数，用空格分隔。如果有多种满足条件的解，输出任意合法解即可。

Examples
Input
2
Output
1 3
5 4
Input
3
Output
1 5 9
4 7 8
3 2 11
Note

本题输出数据量较大，请在程序开头添加以下语句以关闭输入输出流同步，加快输出速度： 


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