There is a graph of $$$n^2$$$ vertices, where vertices are labeled by integer pairs $$$(r,c)$$$ such that $$$1 \le r,c \le n$$$. Vertices $$$(r_1,c_1)$$$ and $$$(r_2,c_2)$$$ are directly connected if and only if $$$(r_1-r_2)^2+(c_1-c_2)^2=\color{red}{13}$$$. This graph is called the Zebra Graph of dimensions $$$n \times n$$$.

Please find a subset of vertices $$$S$$$ in the Zebra Graph of dimensions $$$n \times n$$$, which satisfies the following condition.

The graph induced$$$^{\text{∗}}$$$ by the subset $$$S$$$ is isomorphic to a cycle graph of at least $$$\left\lfloor{\frac{n^2}{e}}\right\rfloor$$$ vertices$$$^{\text{†}}$$$.

It can be shown that such a subset of vertices exists under the constraints of this problem.

$$$^{\text{∗}}$$$The induced graph of a subset of vertices $$$X$$$ is a graph that contains all vertices in $$$X$$$ and all edges whose both endpoints are in $$$X$$$.

$$$^{\text{†}}$$$Here, $$$e$$$ is the mathematical constant equal to the limit $$$\lim \limits_{n \to \infty} \left ({1 + \frac{1}{n}} \right )^n \approx 2.71828182$$$. Note that the value of $$$\frac{1}{e}$$$ is approximately $$$0.36787944$$$.

Input

The first and only line of input contains a single integer $$$n$$$ ($$$n\in \{5,1001\}$$$).

There are only two input files for this problem:

The first input file (the example input) has $$$n=5$$$;
The second input file has $$$n=1001$$$.

Hacks are disabled for this problem.

Output

Output $$$n$$$ lines, each containing a string $$$s_i$$$ of length $$$n$$$ denoting the $$$i$$$-th row of the graph. If the vertex $$$(r,c)$$$ is an element of $$$S$$$, then the $$$c$$$-th letter of $$$s_r$$$ should be '1'. Otherwise, the $$$c$$$-th letter of $$$s_r$$$ should be '0'.

If there are multiple solutions, print any of them.

Note

For the example output, the induced graph corresponding to the subset $$$S$$$ is shown below.

$\text{[math]}$

This graph is isomorphic to the cycle graph $$$C_{16}$$$ consisting of $$$16$$$ vertices. As $$$16 \ge \left\lfloor{\frac{n^2}{e}}\right\rfloor = 9$$$, the output satisfies the problem's condition.

Codeforces Heuristic Contest 1001

Examples