In the W Kingdom, there are $n$ cities, and a courier company delivers packages between any two distinct cities. As the general manager of the courier company, you intend to divide the company into several departments and have these departments compete with each other to improve delivery efficiency.

Dividing the company into departments is not an easy task, as many factors must be considered. For two distinct cities $i$ and $j$, if $i \to j$ and $j \to i$ are handled by two different departments, the department that completes a delivery will have nothing to do on the return trip, which wastes time. For three distinct cities $i, j, k$, if all six delivery routes between them are handled by the same department, you feel that this department has monopolized the courier transport between these three cities, which is detrimental to the company as a whole. Therefore, you stipulate:

• For any two distinct cities $i$ and $j$, $i \to j$ and $j \to i$ must be handled by the same department.
• For any three distinct cities $i, j, k$, the six delivery relationships between them cannot all be handled by the same department.

Since having too many departments is disadvantageous for company management, you need to find the minimum number of departments $m$.

Input

A single integer $n$.

Output

You need to provide a solution to prove your answer. You must output $n$ lines, each containing $n$ integers. The integer $A_{i,j}$ in the $i$-th row and $j$-th column represents that the courier transport between city $i$ and city $j$ is handled by the $A_{i,j}$-th department.

Formally, assuming the minimum number of divisions you found is $m$, the matrix $A$ you output must satisfy the following properties:

• For all $i, j$ where $i \neq j$, $1 \le A_{i,j} \le m$ and $A_{i,j}$ is an integer.
• For all $i, j$, $A_{i,j} = A_{j,i}$.
• For all $i$, $A_{i,i} = 0$.
• For all $i, j, k$ where $i < j < k$, $A_{i,j}, A_{i,k}, A_{j,k}$ are not all identical.

You do not need to output $m$; the maximum value among the numbers you output will automatically be taken as $m$ during evaluation.

Examples

Input 1

3

Output 1

0 1 2
1 0 1
2 1 0

Constraints

This is a traditional problem, but the constraints in the table are $n=$ rather than $n \le$.

If your output solution is invalid, you will receive 0 points for that test case.

If the $m$ corresponding to your output solution is not the minimum number of divisions, you will receive 0 points for that test case.

Otherwise, the information for each test case is as follows: