There is a rectangle divided into an $n \times n$ grid. You need to color some of the cells black, subject to the following requirements:

• No two black cells can share a common edge.
• The set of non-black cells must be 4-connected.

Find the maximum number of cells that can be colored black.

Although an optimal solution exists for this problem, for the sake of your health, this is an output-only problem with partial scoring.

Input

A single integer $n$.

Output

$n$ lines, each containing a $01$ string of length $n$, where $1$ represents a black cell and $0$ represents a non-black cell.

Examples

Input 1

5

Output 1

10101
00000
10101
00000
10101

Constraints

There are $10$ test cases in total, where $n$ is guaranteed to be $300, 301, 302, 303, 304, 305, 306, 307, 308, 309$ respectively.

For each $n$, let $a_n$ be the number of black cells in the optimal solution, and $b_n$ be the number of black cells in your output. Note: There is a corresponding sequence on OEIS, but it is incorrect.

• If $b_n = a_n$, you will receive $10$ points.
• If $a_n - 1 \leq b_n < a_n$, you will receive $9.5$ points.
• If $a_n - 2 \leq b_n < a_n - 1$, you will receive $9$ points.
• If $a_n - 3 \leq b_n < a_n - 2$, you will receive $8.5$ points.
• If $a_n - 5 \leq b_n < a_n - 3$, you will receive $8$ points.
• If $a_n - 10 \leq b_n < a_n - 5$, you will receive $7.5$ points.
• If $a_n - 20 \leq b_n < a_n - 10$, you will receive $7$ points.
• If $a_n - 30 \leq b_n < a_n - 20$, you will receive $6$ points.
• If $a_n - 40 \leq b_n < a_n - 30$, you will receive $5$ points.
• If $a_n - 60 \leq b_n < a_n - 40$, you will receive $4$ points.
• If $a_n - 80 \leq b_n < a_n - 60$, you will receive $3$ points.
• If $a_n - 100 \leq b_n < a_n - 80$, you will receive $2$ points.
• If $a_n - 300 \leq b_n < a_n - 100$, you will receive $1$ point.