Knight’s Tour

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.

Examples

Input
Output
5
0 17 4 9 2 5 10 1 18 13 16 21 12 3 8 11 6 23 14 19 22 15 20 7 24

Constraints

Time limit: 10 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue