1 0
2 1
3 10
4 11
5 100
6 101
7 110
8 111
9 1000
10 1001
11 1100
12 1101
13 10000
14 10001
15 10100
16 10101
17 11000
18 11001
19 11100
20 11101
21 100000
22 100001
23 101100
24 101101
25 110000
26 110001
27 111100
28 111101
29 1000000
30 1000001
31 1010000
32 1010001
33 1100000
34 1100001
35 1110000
36 1110001
37 10000000
38 10000001
39 10010000
40 10010001
41 11000000
42 11000001
43 11010000
44 11010001
45 100000000
46 100000001
47 101000000
48 101000001
49 110000000
50 110000001
51 111000000
52 111000001
53 1000000000
54 1000000001
55 1011000000
56 1011000001
57 1100000000
58 1100000001
59 1111000000
60 1111000001
61 10000000000
62 10000000001
63 10011000000
64 10011000001
65 10100000000
66 10100000001
67 10111000000
68 10111000001
69 11000000000
70 11000000001
71 11011000000
72 11011000001
73 11100000000
74 11100000001
75 11111000000
76 11111000001
77 100000000000
78 100000000001
79 100100000000
80 100100000001
81 101011000000
82 101011000001
83 101111000000
84 101111000001
85 110000000000
86 110000000001
87 110100000000
88 110100000001
89 111011000000
90 111011000001
91 111111000000
92 111111000001
93 1000000000000
94 1000000000001
95 1000100000000
96 1000100000001
97 1001011000000
98 1001011000001
99 1001111000000
100 1001111000001
101 1010000000000
102 1010000000001
103 1010100000000
104 1010100000001
105 1011011000000
106 1011011000001
107 1011111000000
108 1011111000001
109 1100000000000
110 1100000000001
111 1100100000000
112 1100100000001
113 1101011000000
114 1101011000001
115 1101111000000
116 1101111000001
117 1110000000000
118 1110000000001
119 1110100000000
120 1110100000001
121 1111011000000
122 1111011000001
123 1111111000000
124 1111111000001
125 10000000000000
126 10000000000001
127 10001111000000
128 10001111000001
129 10010100000000
130 10010100000001
131 10011011000000
132 10011011000001
133 10100100000000
134 10100100000001
135 10101011000000
136 10101011000001
137 10110000000000
138 10110000000001
139 10111111000000
140 10111111000001
141 11000000000000
142 11000000000001
143 11001111000000
144 11001111000001
145 11010100000000
146 11010100000001
147 11011011000000
148 11011011000001
149 11100100000000
150 11100100000001
151 11101011000000
152 11101011000001
153 11110000000000
154 11110000000001
155 11111111000000
156 11111111000001
157 100000000000000
158 100000000000001
159 100001111000000
160 100001111000001
161 100011011000000
162 100011011000001
163 100101011000000
164 100101011000001
165 101000000000000
166 101000000000001
167 101001111000000
168 101001111000001
169 101011011000000
170 101011011000001
171 101101011000000
172 101101011000001
173 110000000000000
174 110000000000001
175 110001111000000
176 110001111000001
177 110011011000000
178 110011011000001
179 110101011000000
180 110101011000001
181 111000000000000
182 111000000000001
183 111001111000000
184 111001111000001
185 111011011000000
186 111011011000001
187 111101011000000
188 111101011000001
189 1000000000000000
190 1000000000000001
191 1001000000000000
192 1001000000000001
193 1010001111000000
194 1010001111000001
195 1010011011000000
196 1010011011000001
197 1010101011000000
198 1010101011000001
199 1011001111000000
200 1011001111000001
201 1011011011000000
202 1011011011000001
203 1011101011000000
204 1011101011000001
205 1100000000000000
206 1100000000000001
207 1101000000000000
208 1101000000000001
209 1110001111000000
210 1110001111000001
211 1110011011000000
212 1110011011000001
213 1110101011000000
214 1110101011000001
215 1111001111000000
216 1111001111000001
217 1111011011000000
218 1111011011000001
219 1111101011000000
220 1111101011000001
221 10000000000000000
222 10000000000000001
223 10010101011000000
224 10010101011000001
225 10011001111000000
226 10011001111000001
227 10011011011000000
228 10011011011000001
229 10100000000000000
230 10100000000000001
231 10110101011000000
232 10110101011000001
233 10111001111000000
234 10111001111000001
235 10111011011000000
236 10111011011000001
237 11000000000000000
238 11000000000000001
239 11010101011000000
240 11010101011000001
241 11011001111000000
242 11011001111000001
243 11011011011000000
244 11011011011000001
245 11100000000000000
246 11100000000000001
247 11110101011000000
248 11110101011000001
249 11111001111000000
250 11111001111000001
251 11111011011000000
252 11111011011000001
253 100000000000000000
254 100000000000000001
255 100010101011000000
256 100010101011000001
257 100011001111000000
258 100011001111000001
259 100111011011000000
260 100111011011000001
261 101011011011000000
262 101011011011000001
263 101100000000000000
264 101100000000000001
265 101110101011000000
266 101110101011000001
267 101111001111000000
268 101111001111000001
269 110000000000000000
270 110000000000000001
271 110010101011000000
272 110010101011000001
273 110011001111000000
274 110011001111000001
275 110111011011000000
276 110111011011000001
277 111011011011000000
278 111011011011000001
279 111100000000000000
280 111100000000000001
281 111110101011000000
282 111110101011000001
283 111111001111000000
284 111111001111000001
285 1000000000000000000
286 1000000000000000001
287 1000011001111000000
288 1000011001111000001
289 1000111011011000000
290 1000111011011000001
291 1001100000000000000
292 1001100000000000001
293 1001111001111000000
294 1001111001111000001
295 1010000000000000000
296 1010000000000000001
297 1010011001111000000
298 1010011001111000001
299 1010111011011000000
300 1010111011011000001
301 1011100000000000000
302 1011100000000000001
303 1011111001111000000
304 1011111001111000001
305 1100000000000000000
306 1100000000000000001
307 1100011001111000000
308 1100011001111000001
309 1100111011011000000
310 1100111011011000001
311 1101100000000000000
312 1101100000000000001
313 1101111001111000000
314 1101111001111000001
315 1110000000000000000
316 1110000000000000001
317 1110011001111000000
318 1110011001111000001
319 1110111011011000000
320 1110111011011000001
321 1111100000000000000
322 1111100000000000001
323 1111111001111000000
324 1111111001111000001
325 10000000000000000000
326 10000000000000000001
327 10000011001111000000
328 10000011001111000001
329 10000111011011000000
330 10000111011011000001
331 10001100000000000000
332 10001100000000000001
333 10001111001111000000
334 10001111001111000001
335 10010000000000000000
336 10010000000000000001
337 10010011001111000000
338 10010011001111000001
339 10010111011011000000
340 10010111011011000001
341 10011100000000000000
342 10011100000000000001
343 10011111001111000000
344 10011111001111000001
345 11000000000000000000
346 11000000000000000001
347 11000011001111000000
348 11000011001111000001
349 11000111011011000000
350 11000111011011000001
351 11001100000000000000
352 11001100000000000001
353 11001111001111000000
354 11001111001111000001
355 11010000000000000000
356 11010000000000000001
357 11010011001111000000
358 11010011001111000001
359 11010111011011000000
360 11010111011011000001
361 11011100000000000000
362 11011100000000000001
363 11011111001111000000
364 11011111001111000001
365 100000000000000000000
366 100000000000000000001
367 100000111011011000000
368 100000111011011000001
369 100001100000000000000
370 100001100000000000001
371 100010000000000000000
372 100010000000000000001
373 100010111011011000000
374 100010111011011000001
375 100011100000000000000
376 100011100000000000001
377 101000000000000000000
378 101000000000000000001
379 101000111011011000000
380 101000111011011000001
381 101001100000000000000
382 101001100000000000001
383 101010000000000000000
384 101010000000000000001
385 101010111011011000000
386 101010111011011000001
387 101011100000000000000
388 101011100000000000001
389 110000000000000000000
390 110000000000000000001
391 110000111011011000000
392 110000111011011000001
393 110001100000000000000
394 110001100000000000001
395 110010000000000000000
396 110010000000000000001
397 110010111011011000000
398 110010111011011000001
399 110011100000000000000
400 110011100000000000001
401 111000000000000000000
402 111000000000000000001
403 111000111011011000000
404 111000111011011000001
405 111001100000000000000
406 111001100000000000001
407 111010000000000000000
408 111010000000000000001
409 111010111011011000000
410 111010111011011000001
411 111011100000000000000
412 111011100000000000001
413 1000000000000000000000
414 1000000000000000000001
415 1000001100000000000000
416 1000001100000000000001
417 1000010000000000000000
418 1000010000000000000001
419 1000011100000000000000
420 1000011100000000000001
421 1001000111011011000000
422 1001000111011011000001
423 1001010111011011000000
424 1001010111011011000001
425 1010000111011011000000
426 1010000111011011000001
427 1010010111011011000000
428 1010010111011011000001
429 1011000000000000000000
430 1011000000000000000001
431 1011001100000000000000
432 1011001100000000000001
433 1011010000000000000000
434 1011010000000000000001
435 1011011100000000000000
436 1011011100000000000001
437 1100000000000000000000
438 1100000000000000000001
439 1100001100000000000000
440 1100001100000000000001
441 1100010000000000000000
442 1100010000000000000001
443 1100011100000000000000
444 1100011100000000000001
445 1101000111011011000000
446 1101000111011011000001
447 1101010111011011000000
448 1101010111011011000001
449 1110000111011011000000
450 1110000111011011000001
451 1110010111011011000000
452 1110010111011011000001
453 1111000000000000000000
454 1111000000000000000001
455 1111001100000000000000
456 1111001100000000000001
457 1111010000000000000000
458 1111010000000000000001
459 1111011100000000000000
460 1111011100000000000001
461 10000000000000000000000
462 10000000000000000000001
463 10000011100000000000000
464 10000011100000000000001
465 10001010111011011000000
466 10001010111011011000001
467 10010010111011011000000
468 10010010111011011000001
469 10011001100000000000000
470 10011001100000000000001
471 10011010000000000000000
472 10011010000000000000001
473 10100000000000000000000
474 10100000000000000000001
475 10100011100000000000000
476 10100011100000000000001
477 10101010111011011000000
478 10101010111011011000001
479 10110010111011011000000
480 10110010111011011000001
481 10111001100000000000000
482 10111001100000000000001
483 10111010000000000000000
484 10111010000000000000001
485 11000000000000000000000
486 11000000000000000000001
487 11000011100000000000000
488 11000011100000000000001
489 11001010111011011000000
490 11001010111011011000001
491 11010010111011011000000
492 11010010111011011000001
493 11011001100000000000000
494 11011001100000000000001
495 11011010000000000000000
496 11011010000000000000001
497 11100000000000000000000
498 11100000000000000000001
499 11100011100000000000000
500 11100011100000000000001
501 11101010111011011000000
502 11101010111011011000001
503 11110010111011011000000
504 11110010111011011000001
505 11111001100000000000000
506 11111001100000000000001
507 11111010000000000000000
508 11111010000000000000001
509 100000000000000000000000
510 100000000000000000000001
511 100000011100000000000000
512 100000011100000000000001
513 100001010111011011000000
514 100001010111011011000001
515 100011010000000000000000
516 100011010000000000000001
517 100100000000000000000000
518 100100000000000000000001
519 100100011100000000000000
520 100100011100000000000001
521 100101010111011011000000
522 100101010111011011000001
523 100111010000000000000000
524 100111010000000000000001
525 101010010111011011000000
526 101010010111011011000001
527 101011001100000000000000
528 101011001100000000000001
529 101110010111011011000000
530 101110010111011011000001
531 101111001100000000000000
532 101111001100000000000001
533 110000000000000000000000
534 110000000000000000000001
535 110000011100000000000000
536 110000011100000000000001
537 110001010111011011000000
538 110001010111011011000001
539 110011010000000000000000
540 110011010000000000000001
541 110100000000000000000000
542 110100000000000000000001
543 110100011100000000000000
544 110100011100000000000001
545 110101010111011011000000
546 110101010111011011000001
547 110111010000000000000000
548 110111010000000000000001
549 111010010111011011000000
550 111010010111011011000001
551 111011001100000000000000
552 111011001100000000000001
553 111110010111011011000000
554 111110010111011011000001
555 111111001100000000000000
556 111111001100000000000001
557 1000000000000000000000000
558 1000000000000000000000001
559 1000100011100000000000000
560 1000100011100000000000001
561 1000101010111011011000000
562 1000101010111011011000001
563 1000111010000000000000000
564 1000111010000000000000001
565 1001010010111011011000000
566 1001010010111011011000001
567 1001111001100000000000000
568 1001111001100000000000001
569 1010000000000000000000000
570 1010000000000000000000001
571 1010100011100000000000000
572 1010100011100000000000001
573 1010101010111011011000000
574 1010101010111011011000001
575 1010111010000000000000000
576 1010111010000000000000001
577 1011010010111011011000000
578 1011010010111011011000001
579 1011111001100000000000000
580 1011111001100000000000001
581 1100000000000000000000000
582 1100000000000000000000001
583 1100100011100000000000000
584 1100100011100000000000001
585 1100101010111011011000000
586 1100101010111011011000001
587 1100111010000000000000000
588 1100111010000000000000001
589 1101010010111011011000000
590 1101010010111011011000001
591 1101111001100000000000000
592 1101111001100000000000001
593 1110000000000000000000000
594 1110000000000000000000001
595 1110100011100000000000000
596 1110100011100000000000001
597 1110101010111011011000000
598 1110101010111011011000001
599 1110111010000000000000000
600 1110111010000000000000001
601 1111010010111011011000000
602 1111010010111011011000001
603 1111111001100000000000000
604 1111111001100000000000001
605 10000000000000000000000000
606 10000000000000000000000001
607 10000100011100000000000000
608 10000100011100000000000001
609 10000111010000000000000000
610 10000111010000000000000001
611 10001010010111011011000000
612 10001010010111011011000001
613 10001111001100000000000000
614 10001111001100000000000001
615 10010101010111011011000000
616 10010101010111011011000001
617 10100101010111011011000000
618 10100101010111011011000001
619 10110000000000000000000000
620 10110000000000000000000001
621 10110100011100000000000000
622 10110100011100000000000001
623 10110111010000000000000000
624 10110111010000000000000001
625 10111010010111011011000000
626 10111010010111011011000001
627 10111111001100000000000000
628 10111111001100000000000001
629 11000000000000000000000000
630 11000000000000000000000001
631 11000100011100000000000000
632 11000100011100000000000001
633 11000111010000000000000000
634 11000111010000000000000001
635 11001010010111011011000000
636 11001010010111011011000001
637 11001111001100000000000000
638 11001111001100000000000001
639 11010101010111011011000000
640 11010101010111011011000001
641 11100101010111011011000000
642 11100101010111011011000001
643 11110000000000000000000000
644 11110000000000000000000001
645 11110100011100000000000000
646 11110100011100000000000001
647 11110111010000000000000000
648 11110111010000000000000001
649 11111010010111011011000000
650 11111010010111011011000001
651 11111111001100000000000000
652 11111111001100000000000001
653 100000000000000000000000000
654 100000000000000000000000001
655 100000100011100000000000000
656 100000100011100000000000001
657 100001111001100000000000000
658 100001111001100000000000001
659 100010101010111011011000000
660 100010101010111011011000001
661 100110000000000000000000000
662 100110000000000000000000001
663 100110100011100000000000000
664 100110100011100000000000001
665 100111111001100000000000000
666 100111111001100000000000001
667 101000000000000000000000000
668 101000000000000000000000001
669 101000100011100000000000000
670 101000100011100000000000001
671 101001111001100000000000000
672 101001111001100000000000001
673 101010101010111011011000000
674 101010101010111011011000001
675 101110000000000000000000000
676 101110000000000000000000001
677 101110100011100000000000000
678 101110100011100000000000001
679 101111111001100000000000000
680 101111111001100000000000001
681 110000000000000000000000000
682 110000000000000000000000001
683 110000100011100000000000000
684 110000100011100000000000001
685 110001111001100000000000000
686 110001111001100000000000001
687 110010101010111011011000000
688 110010101010111011011000001
689 110110000000000000000000000
690 110110000000000000000000001
691 110110100011100000000000000
692 110110100011100000000000001
693 110111111001100000000000000
694 110111111001100000000000001
695 111000000000000000000000000
696 111000000000000000000000001
697 111000100011100000000000000
698 111000100011100000000000001
699 111001111001100000000000000
700 111001111001100000000000001
701 111010101010111011011000000
702 111010101010111011011000001
703 111110000000000000000000000
704 111110000000000000000000001
705 111110100011100000000000000
706 111110100011100000000000001
707 111111111001100000000000000
708 111111111001100000000000001
709 1000000000000000000000000000
710 1000000000000000000000000001
711 1000010101010111011011000000
712 1000010101010111011011000001
713 1000110100011100000000000000
714 1000110100011100000000000001
715 1000111111001100000000000000
716 1000111111001100000000000001
717 1001000000000000000000000000
718 1001000000000000000000000001
719 1001010101010111011011000000
720 1001010101010111011011000001
721 1001110100011100000000000000
722 1001110100011100000000000001
723 1001111111001100000000000000
724 1001111111001100000000000001
725 1010000100011100000000000000
726 1010000100011100000000000001
727 1010001111001100000000000000
728 1010001111001100000000000001
729 1010110000000000000000000000
730 1010110000000000000000000001
731 1011000100011100000000000000
732 1011000100011100000000000001
733 1011001111001100000000000000
734 1011001111001100000000000001
735 1011110000000000000000000000
736 1011110000000000000000000001
737 1100000000000000000000000000
738 1100000000000000000000000001
739 1100010101010111011011000000
740 1100010101010111011011000001
741 1100110100011100000000000000
742 1100110100011100000000000001
743 1100111111001100000000000000
744 1100111111001100000000000001
745 1101000000000000000000000000
746 1101000000000000000000000001
747 1101010101010111011011000000
748 1101010101010111011011000001
749 1101110100011100000000000000
750 1101110100011100000000000001
751 1101111111001100000000000000
752 1101111111001100000000000001
753 1110000100011100000000000000
754 1110000100011100000000000001
755 1110001111001100000000000000
756 1110001111001100000000000001
757 1110110000000000000000000000
758 1110110000000000000000000001
759 1111000100011100000000000000
760 1111000100011100000000000001
761 1111001111001100000000000000
762 1111001111001100000000000001
763 1111110000000000000000000000
764 1111110000000000000000000001
765 10000000000000000000000000000
766 10000000000000000000000000001
767 10001000000000000000000000000
768 10001000000000000000000000001
769 10100000000000000000000000000
770 10100000000000000000000000001
771 10101000000000000000000000000
772 10101000000000000000000000001
773 11000000000000000000000000000
774 11000000000000000000000000001
775 11001000000000000000000000000
776 11001000000000000000000000001
777 11100000000000000000000000000
778 11100000000000000000000000001
779 11101000000000000000000000000
780 11101000000000000000000000001
781 100000000000000000000000000000
782 100000000000000000000000000001
783 100101000000000000000000000000
784 100101000000000000000000000001
785 101001000000000000000000000000
786 101001000000000000000000000001
787 101100000000000000000000000000
788 101100000000000000000000000001
789 110000000000000000000000000000
790 110000000000000000000000000001
791 110101000000000000000000000000
792 110101000000000000000000000001
793 111001000000000000000000000000
794 111001000000000000000000000001
795 111100000000000000000000000000
796 111100000000000000000000000001
797 1000000000000000000000000000000
798 1000000000000000000000000000001
799 1000101000000000000000000000000
800 1000101000000000000000000000001
801 1001001000000000000000000000000
802 1001001000000000000000000000001
803 1010000000000000000000000000000
804 1010000000000000000000000000001
805 1010101000000000000000000000000
806 1010101000000000000000000000001
807 1011001000000000000000000000000
808 1011001000000000000000000000001
809 1100000000000000000000000000000
810 1100000000000000000000000000001
811 1100101000000000000000000000000
812 1100101000000000000000000000001
813 1101001000000000000000000000000
814 1101001000000000000000000000001
815 1110000000000000000000000000000
816 1110000000000000000000000000001
817 1110101000000000000000000000000
818 1110101000000000000000000000001
819 1111001000000000000000000000000
820 1111001000000000000000000000001
821 10000000000000000000000000000000
822 10000000000000000000000000000001
823 10010000000000000000000000000000
824 10010000000000000000000000000001
825 10100101000000000000000000000000
826 10100101000000000000000000000001
827 10101001000000000000000000000000
828 10101001000000000000000000000001
829 10110101000000000000000000000000
830 10110101000000000000000000000001
831 10111001000000000000000000000000
832 10111001000000000000000000000001
833 11000000000000000000000000000000
834 11000000000000000000000000000001
835 11010000000000000000000000000000
836 11010000000000000000000000000001
837 11100101000000000000000000000000
838 11100101000000000000000000000001
839 11101001000000000000000000000000
840 11101001000000000000000000000001
841 11110101000000000000000000000000
842 11110101000000000000000000000001
843 11111001000000000000000000000000
844 11111001000000000000000000000001
845 100000000000000000000000000000000
846 100000000000000000000000000000001
847 100110101000000000000000000000000
848 100110101000000000000000000000001
849 100111001000000000000000000000000
850 100111001000000000000000000000001