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 ≤ 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

Difficulty: competition

Starter code:

Solutions:
k = int(input())
p = [['0'] * 100 for j in range(100)]
g = lambda n: n * (n * n - 1) // 6
i = n = 0
while g(n + 1) <= k: n += 1
while i < n + 1:
    for j in range(i): p[i][j] = p[j][i] = '1'
    i += 1
k -= g(n)
g = lambda n: n * n - n >> 1
while k:
    n = 0
    while g(n + 1) <= k: n += 1
    for j in range(n): p[i][j] = p[j][i] = '1'
    k -= g(n)
    i += 1
print(i)
for j in range(i): print(''.join(p[j][:i]))

k = int(input())
p = [['0'] * 100 for i in range(100)]
j = n = 0
while j < k:
    for i in range(n):
        if j + i > k: break
        p[n][i] = p[i][n] = '1'
        j += i
    n += 1
print(n)
for i in range(n): print(''.join(p[i][:n]))

n, k = 0, int(input())
p = [['0'] * 100 for i in range(100)]
while k:
    for i in range(n):
        if i > k: break
        p[n][i] = p[i][n] = '1'
        k -= i
    n += 1
print(n)
for i in range(n): print(''.join(p[i][:n]))

n, k = 0, int(input())
p = [['0'] * 100 for i in range(100)]
while k:
    for i in range(n):
        if i > k: break
        p[n][i] = p[i][n] = '1'
        k -= i
    n += 1
print(n)
for i in range(n): print(''.join(p[i][:n]))


n, k = 0, int(input())
p = [['0'] * 100 for i in range(100)]
while k:
    for i in range(n):
        if i > k: break
        p[n][i] = p[i][n] = '1'
        k -= i
    n += 1
print(n)
for i in range(n): print(''.join(p[i][:n]))


n, k = 0, int(input())
p = [['0'] * 100 for i in range(100)]
while k:
    for i in range(n):
        if i > k: break
        p[n][i] = p[i][n] = '1'
        k -= i
    n += 1
print(n)
for i in range(n): print(''.join(p[i][:n]))


n, k = 0, int(input())
p = [['0'] * 100 for i in range(100)]
while k:
    for i in range(n):
        if i > k: break
        p[n][i] = p[i][n] = '1'
        k -= i
    n += 1
print(n)
for i in range(n): print(''.join(p[i][:n]))


n, k = 0, int(input())
p = [['0'] * 100 for i in range(100)]
while k:
    for i in range(n):
        if i > k: break
        p[n][i] = p[i][n] = '1'
        k -= i
    n += 1
print(n)
for i in range(n): print(''.join(p[i][:n]))


n, k = 0, int(input())
p = [['0'] * 100 for i in range(100)]
while k:
    for i in range(n):
        if i > k: break
        p[n][i] = p[i][n] = '1'
        k -= i
    n += 1
print(n)
for i in range(n): print(''.join(p[i][:n]))


n, k = 0, int(input())
p = [['0'] * 100 for i in range(100)]
while k:
    for i in range(n):
        if i > k: break
        p[n][i] = p[i][n] = '1'
        k -= i
    n += 1
print(n)
for i in range(n): print(''.join(p[i][:n]))


n, k = 0, int(input())
p = [['0'] * 100 for i in range(100)]
while k:
    for i in range(n):
        if i > k: break
        p[n][i] = p[i][n] = '1'
        k -= i
    n += 1
print(n)
for i in range(n): print(''.join(p[i][:n]))


n, k = 0, int(input())

p = [['0'] * 100 for i in range(100)]

while k:

    for i in range(n):

        if i > k: break

        p[n][i] = p[i][n] = '1'

        k -= i

    n += 1

print(n)

for i in range(n): print(''.join(p[i][:n]))


n , k = 0 , int(input())
p=[['0']*100 for i in range(100)]
while k:
	for i in range(n):
		if i>k:
			break
		p[n][i]=p[i][n]='1'
		k=k-i
	n+=1
print(n)
for i in range(n): print(''.join(p[i][:n]))

n , k = 0 , int(input())
p=[['0']*100 for i in range(100)]
while k:
 for i in range(n):
  if i>k:
   break
  p[n][i]=p[i][n]='1'
  k=k-i
 n+=1
print(n)
for i in range(n): print(''.join(p[i][:n]))

# https://codeforces.com/contest/232/problem/A
# WA 

def f_3(n):
    return n * (n-1) * (n-2) // 6

def f_2(n):
    return n * (n-1) // 2

a_3   = [f_3(i) for i in range(100)]
a_2   = [f_2(i) for i in range(100)]

def find_2(x, a):
    arr = []
    cur = len(a) - 1
    
    while x > 0:
        while x < a[cur]:
            cur -= 1
        arr.append(cur)
        x -= a[cur]
        
    return arr

def find_3(x, a):
    cur = len(a) - 1
    
    while x < a[cur]:
        cur -= 1
    
    x -= a[cur]

    return cur, x    

def build(x):
    base, remain = find_3(x, a_3)
    arr          = find_2(remain, a_2)
    
    n  = base 
    #print(base, arr)
    
    if len(arr) > 0:
        n += len(arr)
        
    m  = [[0]*n for _ in range(n)]

    for i in range(base):
        for j in range(base):
            if i == j:
                continue
            m[i][j] = 1
            m[j][i] = 1
        
    for i, x in enumerate(arr):
        for j in range(x):
            m[base+i][j] = 1
            m[j][base+i] = 1
        
    return m        

def pr(m):
    for i in range(len(m)):
        print(''.join([str(x) for x in m[i]]))

k  = int(input())
m  = build(k)

print(len(m))
pr(m)