#include <bits/stdc++.h>
using namespace std;
long long C(long long n, long long k) {
  long long i, isumn = 1, isumk = 1, isumnk = 1;
  for (i = n - k + 1; i <= n; i++) {
    isumn *= i;
  }
  for (i = 1; i <= k; i++) {
    isumk *= i;
  }
  return (isumn / isumk);
}
long long point = 0, c, a, b, d[1005][1005], point1;
int main() {
  int i, j;
  cin >> a;
  for (i = 3; i <= 100; i++) {
    if (C(i, 3) > a) {
      point = i - 1;
      break;
    }
  }
  if (C(point, 3) == a) {
    for (i = 1; i <= point; i++) {
      for (j = 1; j <= point; j++) {
        if (i == j)
          d[i][j] = 0;
        else
          d[i][j] = 1;
      }
    }
    cout << point << "\n";
    for (i = 1; i <= point; i++) {
      for (j = 1; j <= point; j++) cout << d[i][j];
      cout << "\n";
    }
    return 0;
  } else {
    a = a - C(point, 3);
    for (i = 1; i <= point; i++) {
      for (j = 1; j <= point; j++) {
        if (i == j)
          d[i][j] = 0;
        else
          d[i][j] = 1;
      }
    }
    point1 = point + 1;
    while (a > 0) {
      d[point1][1] = 1;
      d[1][point1] = 1;
      for (i = 2; i <= point; i++) {
        if ((i - 1) * i / 2 <= a) {
          d[point1][i] = 1;
          d[i][point1] = 1;
        }
        if (a == 0) break;
        if ((i - 1) * i / 2 > a) {
          a = a - (i - 2) * (i - 1) / 2;
          break;
        }
      }
      if (a == 0)
        break;
      else
        point1++;
    }
    cout << point1 << "\n";
    for (i = 1; i <= point1; i++) {
      for (j = 1; j <= point1; j++) {
        if (i == j) {
          cout << "0";
        } else {
          if (d[i][j] == 1)
            cout << "1";
          else
            cout << "0";
        }
      }
      cout << "\n";
    }
  }
}

### Prompt

Develop a solution in CPP to the problem described below:

John 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 ≤ 105) — 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long C(long long n, long long k) {
  long long i, isumn = 1, isumk = 1, isumnk = 1;
  for (i = n - k + 1; i <= n; i++) {
    isumn *= i;
  }
  for (i = 1; i <= k; i++) {
    isumk *= i;
  }
  return (isumn / isumk);
}
long long point = 0, c, a, b, d[1005][1005], point1;
int main() {
  int i, j;
  cin >> a;
  for (i = 3; i <= 100; i++) {
    if (C(i, 3) > a) {
      point = i - 1;
      break;
    }
  }
  if (C(point, 3) == a) {
    for (i = 1; i <= point; i++) {
      for (j = 1; j <= point; j++) {
        if (i == j)
          d[i][j] = 0;
        else
          d[i][j] = 1;
      }
    }
    cout << point << "\n";
    for (i = 1; i <= point; i++) {
      for (j = 1; j <= point; j++) cout << d[i][j];
      cout << "\n";
    }
    return 0;
  } else {
    a = a - C(point, 3);
    for (i = 1; i <= point; i++) {
      for (j = 1; j <= point; j++) {
        if (i == j)
          d[i][j] = 0;
        else
          d[i][j] = 1;
      }
    }
    point1 = point + 1;
    while (a > 0) {
      d[point1][1] = 1;
      d[1][point1] = 1;
      for (i = 2; i <= point; i++) {
        if ((i - 1) * i / 2 <= a) {
          d[point1][i] = 1;
          d[i][point1] = 1;
        }
        if (a == 0) break;
        if ((i - 1) * i / 2 > a) {
          a = a - (i - 2) * (i - 1) / 2;
          break;
        }
      }
      if (a == 0)
        break;
      else
        point1++;
    }
    cout << point1 << "\n";
    for (i = 1; i <= point1; i++) {
      for (j = 1; j <= point1; j++) {
        if (i == j) {
          cout << "0";
        } else {
          if (d[i][j] == 1)
            cout << "1";
          else
            cout << "0";
        }
      }
      cout << "\n";
    }
  }
}

```