Có một quân mã trên bàn cờ ~n \times n~. Với mỗi ô, hãy in ra số bước di chuyển ít nhất mà quân mã cần thực hiện để đến được góc trên bên trái.

Dữ liệu vào

Dòng duy nhất chứa một số nguyên ~n~.

Kết quả

In ra số bước di chuyển cho mỗi ô.

Giới hạn

• ~4 \le n \le 1000~

Ví dụ

Dữ liệu vào:

8

Kết quả:

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