1 1
2 1001
3 10001
4 10101
5 10001001
6 10100001
7 100000001
8 100010001
9 100100101
10 101000101
11 101010101
12 100000101001
13 100010001001
14 100100001001
15 100101001001
16 101000100001
17 101010000001
18 1000000000001
19 1000001000001
20 1000010010001
21 1000100010001
22 1000101010001
23 1001000100101
24 1001010000101
25 1010000000101
26 1010001000101
27 1010010010101
28 1010100010101
29 1010101010101
30 1000000010101001
31 1000001000101001
32 1000010000101001
33 1000010100101001
34 1000100010001001
35 1000101000001001
36 1001000000001001
37 1001000100001001
38 1001001001001001
39 1001010001001001
40 1001010101001001
41 1010000010100001
42 1010001000100001
43 1010010000100001
44 1010010100100001
45 1010100010000001
46 1010101000000001
47 10000000000000001
48 10000000100000001
49 10000001001000001
50 10000010001000001
51 10000010101000001
52 10000100010010001
53 10000101000010001
54 10001000000010001
55 10001000100010001