For technical reasons, some programming languages (Kotlin, C #) will not be available during round 877.
×

No tag edit access

A. Cycles

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputJohn Doe started thinking about graphs. After some thought he decided that he wants to paint an undirected graph, containing exactly *k* cycles of length 3.

A cycle of length 3 is an unordered group of three distinct graph vertices *a*, *b* and *c*, such that each pair of them is connected by a graph edge.

John has been painting for long, but he has not been a success. Help him find such graph. Note that the number of vertices there shouldn't exceed 100, or else John will have problems painting it.

Input

A single line contains an integer *k* (1 ≤ *k* ≤ 10^{5}) — the number of cycles of length 3 in the required graph.

Output

In the first line print integer *n* (3 ≤ *n* ≤ 100) — the number of vertices in the found graph. In each of next *n* lines print *n* characters "0" and "1": the *i*-th character of the *j*-th line should equal "0", if vertices *i* and *j* do not have an edge between them, otherwise it should equal "1". Note that as the required graph is undirected, the *i*-th character of the *j*-th line must equal the *j*-th character of the *i*-th line. The graph shouldn't contain self-loops, so the *i*-th character of the *i*-th line must equal "0" for all *i*.

Examples

Input

1

Output

3

011

101

110

Input

10

Output

5

01111

10111

11011

11101

11110

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2017 23:49:23 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|