G. Geo Sharding
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

For a given integer $$$n$$$, you must color each cell of an $$$n \times n$$$ grid into one of $$$C = 10 + \lfloor\frac{n^2}{100}\rfloor$$$ colors. Each specific color could be used at most 150 times.

For each cell $$$(r, c)$$$, the set of colors used in cells $$$(r_i, c_i)$$$ where $$$(r - r_i)^2 + (c - c_i)^2 \le 100$$$, should contain at most 8 different colors.

Input

The only line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the grid size.

Output

Print $$$n$$$ lines with $$$n$$$ integers $$$1 \le a_{r,c} \le C$$$ in each.

Example
Input
3
Output
1 2 3
4 5 6
7 8 8