Knight route

Given a n * n board with the Knight placed in the first row and first column of an empty board. Moving according to the rules of chess knight, visit each square exactly once.

Print the order of each the cell in which they are visited.

Input

The size of the chess board n (n ≤ 8).

Output

Print the state of the board with knight moves. If the problem has no solution, print "Solution does not exist".

Examples