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 N2 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 N2,
which are numbers of days for which coupons apply.
Participants must cut their tables into N2 cells in order to obtain N2 coupons: one coupon per one day of the camp.
This year, when Dima received his sheet with coupons, he noticed that in the ith row and jth 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 2N2 – 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 N2 days to find such a table. Can you do it in five hours?
The input contains the integer 2 ≤ N ≤ 50.
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.
Problem Author: Sergey Pupyrev
Problem Source: The XIth USU Programing Championship, October 7, 2006