Knight route

You are given a chessboard of size n \times n. A knight is placed in the first row and first column (top-left corner) of an empty board. By following the movement rules for a chess knight, you must visit every cell of the board exactly once.

\InputFileThe size of the chessboard $n$ (1 \leq n \leq 8).

\OutputFilePrint the state of the board with the knight's moves in the order they are visited. If there is no solution, print "Solution does not exist".