You are given an empty n x n chessboard, and a knight is placed on the first square of the board. The knight follows the movement rules of a chess knight and must visit each square on the board exactly once. Your task is to print the order in which the knight visits each square.
Input
The input consists of a single integer n (5 ≤ n ≤ 30), representing the size of the chessboard.
Output
Print n lines, each containing n space-separated integers representing the order in which the knight visits each square on the chessboard. The integers should be in the range from 0 to , indicating the order of visitation. The program can output any valid solution.