On the first day of the Petrozavodsk Training Camp,
every participant is given meal coupons, which can be used
in the dining-hall of the Petrozavodsk State University.
This year the camp lasts for *N*^{2} days,
and there is a separate coupon for each day.
In order to make the coupons, the organizers have printed
tables *N* × *N* on sheets of green paper.
Each table contains numbers from 1 to *N*^{2},
which are numbers of days for which coupons apply.
Participants must cut their tables into *N*^{2} cells in order to obtain *N*^{2} coupons: one coupon per one day of the camp.

This year, when Dima received his sheet with coupons, he noticed that in the *i*th row and *j*th column of the printed table there was the number *N*(*i* – 1) + *j* (rows and columns are numbered from 1). Cells of the table are adjacent if they have a common side. Dima is a mathematician, so he quickly found two adjacent cells with the maximal sum of numbers in them. It turned out that the maximal sum was 2*N*^{2} – 1.
Now Dima wants to find an order of coupons in the table such that the maximal sum of numbers in two adjacent cells is minimal. Dima has *N*^{2} days to find such a table. Can you do it in five hours?

### Input

The input contains the integer 2 ≤ *N* ≤ 50.

### Output

In the first line, output the required minimal value.
Then output a table that provides this minimum by giving
*N* numbers in each of the next *N* lines.
If several answers are possible, you may output any of them.

### Sample

**Problem Author: **Sergey Pupyrev

**Problem Source: **The XIth USU Programing Championship, October 7, 2006