This is an answer-submission problem.

This is a problem that Zha-ke battled for half an hour during IOI 2024 training.

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.

Implementation Details

You do not need to submit a program; you only need to submit your constructed answer.

There are 7 test cases in this problem, each worth 1 point, for a total of 7 points.

Input

An integer $n$.

Output

$n$ lines, each containing a binary 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 7 test cases in total, with $n$ equal to $300, 301, 302, 303, 304, 305, 306$ 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 answer.

If $b_n = a_n$, you will receive 1 point. Otherwise, you will receive 0 points.