Tetris Tiling

You are given an integer $N$. You also have an empty $N \times N$ grid of cells, on top of which you can add tetris pieces in the following way:

1. Select $4$ cells from the grid which correspond to one of the following $8$ shapes:

2. If all $4$ selected cells are empty, then a new tetris piece is placed on top of them.

Any grid obtained through these operations starting from an empty grid is called a tetris tiling.

Task

Find any $N \times N$ tetris tiling which uses the maximum possible number of pieces.

Input data

The first and only line of input contains a single integer $N$, the size of the grid.

Output data

First, output one line containing one integer indicating the maximum number of tetris pieces that can placed on an $N \times N$ grid.

Then, output $N$ lines, each containing $N$ space-separated integers. The $j$-th integer of the $i$-th line is denoted by $A_{i,j}$.

If $A_{i,j} > 0$ then the cell in row $i$ and column $j$ belongs to piece $A_{i,j}$. Otherwise, if $A_{i,j}$ is $0$, the corresponding cell is empty and does not belong to any piece.

If there are multiple solutions which maximizes the number of pieces in the tiling, output any of them.

Constraints and clarifications

• $1 \le N \le 1 \ 000$

Example 1

stdin

2

stdout

0
0 0 
0 0

Example 2

stdin

3

stdout

1
0 1 0
0 1 1
0 0 1

Example 3

stdin

5

stdout

6
1 2 2 2 3
1 1 2 3 3
1 6 0 3 4
6 6 5 4 4
6 5 5 5 4

Explanation

It can be proven that for these values of $N$, there are no tetris tilings that use more pieces than the ones depicted below.