Elegant Square

Time limit2sMemory limit512 MB

Summary

Build an n by n grid of distinct square-free integers, each at most 10^18, where every row and every column has the same product.

Level: Medium7 of 10
Topics: Number theory, Math, Matrix, Implementation
Solved: No attempts yet

Problem

Magic squares are square grids of distinct numbers where every row and column has the same sum. Eve recently learned about them and invented her own version, the elegant square (elegant square).

Eve calls an $n\times n$ square of integers elegant if all of the following conditions hold.

All entries of the square are distinct positive integers.
All integers are square free. That is, no integer is divisible by $t^2$ for any $t > 1$ .
The product of the numbers in any row and any column is the same.

The figure below shows an elegant $3 \times 3$ square.

$\begin{matrix} 1& 21& 10\\ 6& 5& 7\\ 35& 2& 3 \end{matrix}$

All of its entries are distinct positive square free integers, and the product of any row and any column is 210.

Find an $n \times n$ elegant square for Eve. All numbers in the square must not exceed $10^{18}$ . The constraints guarantee that such a square exists.

Input

The input is a single integer $n$ ( $3 \le n \le 30$ ).

Output

Print the $n \times n$ integers of the elegant square you found. Every printed integer must not exceed $10^{18}$ .

Examples1

Example 1
Input
```
3
```
Expected output
```
1 21 10
6 5 7
35 2 3
```