Bạn có một quân mã trên bàn cờ kích thước n × n.

Quân mã di chuyển theo quy tắc chuẩn trong cờ vua: hình chữ L (2 ô theo một hướng, sau đó 1 ô theo hướng vuông góc).

Yêu cầu: Với mỗi ô trên bàn cờ, hãy in ra số bước di chuyển tối thiểu để quân mã từ ô đó đi đến góc trên bên trái (tức ô (0, 0) nếu đánh chỉ số từ 0).

Đầu vào:

Một dòng duy nhất chứa số nguyên ~n~ — kích thước bàn cờ.

Đầu ra:

In ra ~n~ dòng, mỗi dòng gồm ~n~ số nguyên cách nhau bởi dấu cách:

Số nguyên tại vị trí (i, j) là số bước tối thiểu để quân mã từ ô (i, j) đi đến ô (0, 0).

Ràng buộc:

~4 \le n \le 1000~

Ví dụ :

Input:

8

Output:

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