Nhiệm vụ của bạn là xây dựng một lưới \(n \times n\), trong đó mỗi ô chứa số nguyên không âm nhỏ nhất không xuất hiện ở bên trái nó trên cùng hàng hoặc ở phía trên nó trên cùng cột.

Input

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

Output

In ra lưới theo đúng định dạng như ví dụ.

Constraints

• \(1 \le n \le 100\)

Example

5

0 1 2 3 4
1 0 3 2 5
2 3 0 1 6
3 2 1 0 7
4 5 6 7 0