Có một quân mã trên bàn cờ vua \(n \times n\). Với mỗi ô, hãy in số bước đi ít nhất mà quân mã cần để đi tới góc trên bên trái.

Input

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

Output

In số bước đi cho mỗi ô.

Constraints

• \(4 \le n \le 1000\)

Example

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