На ~n \times n~ шахівниці стоїть кінь. Для кожного квадрата виведіть мінімальну кількість ходів, які має зробити кінь, щоб досягти верхнього лівого кута.

Обмеження

• ~4 \le n \le 1000~

Формат вхідних даних

Єдиний рядок містить ціле число ~n~.

Формат вихідних даних

Виведіть кількість ходів для кожного квадрата.

Приклад вхідних даних

8

Приклад вихідних даних

0 3 2 3 2 3 4 5
3 4 1 2 3 4 3 4
2 1 4 3 2 3 4 5
3 2 3 2 3 4 3 4
2 3 2 3 4 3 4 5
3 4 3 4 3 4 5 4
4 3 4 3 4 5 4 5
5 4 5 4 5 4 5 6