Задана шахматная доска n * n. Конь расположен в первой строке первого столбца пустой доски. Следуя шахматным правилам перемещения коня, посетите каждую клетку доски один рах.

Выведите состояние шахматной доски с ходами коня.

Входные данные

Размер шахматной доски n (1 ≤ n ≤ 8).

Выходные данные

Выведите состояние шахматной доски с ходами коня. Если задача не имеет решения, выведите "Solution does not exist".