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² 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², which are numbers of days for which coupons apply. Participants must cut their tables into N² cells in order to obtain N² 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 2N² – 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² 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.