In this problem we consider n × n tables filled with integers from 1 to n² 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 n² 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.

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

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

The primality of the table in the sample output is equal to 3 (this is the primality of its first column).