~L~-кінь(~a,b~) може переміститися з клітинки (~x_1,y_1~) в клітинку (~x_2,y_2~) якщо виконуються одна із вимог:

~x_2=x_1 \pm a~ і ~y_2=y_1 \pm b~

або

~x_2=x_1 \pm b~ і ~y_2=y_1 \pm a~

Наприклад, ~L~-кінь(1,2) або ~L~-кінь(2,1) з червоної клітинки може переміститися в будь-яку зелену.

Дана шахівниця розміром ~n \times n~. Дайте відповідь на запитання для кожної пари (~a,b~), де ~1 \le a,b \le n~:

- Яка мінімальна кількість ходів потрібна для ~L~-кінь(~a,b~), щоб перейти з позиції (0,0) в позицію (n-1,n-1)? Якщо кінь не може дістатися до місця призначення, то виведіть -1.

Відповідь вивести для кожного ~L~-кінь(~a,b~) згідно формату вихідних даних.

Обмеження

• ~5 \le n \le 25~

Input

Вхідний потік містить одне ціле число ~n~ - розмірність шахівниці.

Output

У вихідний потік вивести ~n-1~ рядок. ~i~-й (де ~1 \le i \le n~) рядок містить ~n-1~ цілих чисел, розділених пропуском, які є мінімальною кількістю ходів для ~L~-кінь(~i,j~) для відповідного ~j~ (де ~1 \le j \le n~) щоб перейти з позиції (0,0) в позицію (n-1,n-1).

Наприклад, для ~n=3~ вихідні дані для всіх пар (~i,j~) розтащуються таким чином:

(1,1) (1,2)

(2,1) (2,2)

Sample Input 1

5

Sample Output 1

4 4 2 8 
4 2 4 4 
2 4 -1 -1 
8 4 -1 1

Notes

Приклади можливих ходів для різних ~(i,j)~: