Given a positive integer n, print an n x n matrix where each cell is the minimum distance to any border plus 1.

Input

• One positive integer n.

Output

• Numbers on the same line are separated by exactly one space.

Constraints

• 1 <= n <= 100

Example

Input

5

Output

1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1