ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1985. Prime Square

Time limit: 1.0 second
Memory limit: 64 MB
In this problem we consider n × n tables filled with integers from 1 to n2 in such a way that the following conditions are satisfied.
  1. Each number occurs exactly once in the table.
  2. For each i from 2 to n2 the cells of the table that contain i and i − 1 must have a shared side.
Let’s define a primality of a column as the number of its cells containing prime numbers, and a primality of a table as the maximum primality of all its columns. Find the table with the maximum primality among all tables that satisfy the stated conditions.

Input

The only line contains an integer n (1 ≤ n ≤ 256).

Output

Output the required table. If there are several tables with the maximum primality, you may output any of them.

Sample

inputoutput
4
2 1 12 11
3 16 13 10
4 15 14 9
5 6 7 8 

Notes

The primality of the table in the sample output is equal to 3 (this is the primality of its first column).
Problem Author: Mikhail Rubinchik, special thanks to Alexander Ipatov
Problem Source: Open Ural FU Championship 2013