Lưới Nước Mã

Cho bàn cờ $n\times n$. Với mỗi ô trên bàn cờ, hãy tính số nước đi tối thiểu của quân mã để đến góc trên bên trái (ô $(1,1)$).

Quân mã di chuyển theo kiểu chữ L: 2 ô theo một hướng rồi 1 ô vuông góc (8 hướng có thể).

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$.

Dữ liệu ra

In ra lưới $n\times n$, mỗi ô chứa số nước đi tối thiểu từ ô đó đến $(1,1)$.

Ràng buộc

• $4\le n\le 1000$

Ví dụ