ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

## E. 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
To submit the solution for this problem go to the Problem set: 1985. Prime Square