0 1
1 0
2 1
3 0
4 1
5 0
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 2
15 1
16 2
17 1
18 2
19 1
20 2
21 2
22 2
23 2
24 2
25 2
26 2
27 2
28 3
29 2
30 3
31 2
32 3
33 2
34 3
35 3
36 3
37 3
38 3
39 3
40 3
41 3
42 4
43 3
44 4
45 3
46 4
47 3
48 4
49 4
50 4
51 4
52 4
53 4
54 4
55 4
56 5
57 4
58 5
59 4
60 5
61 4
62 5
63 5
64 5
65 5
66 5
67 5
68 5
69 5
70 6
71 5
72 6
73 5
74 6
75 5
76 6
77 6
78 6
79 6
80 6
81 6
82 6
83 6
84 7
85 6
86 7
87 6
88 7
89 6
90 7
91 7
92 7
93 7
94 7
95 7
96 7
97 7
98 8
99 7
100 8
101 7
102 8
103 7
104 8
105 8
106 8
107 8
108 8
109 8
110 8
111 8
112 9
113 8
114 9
115 8
116 9
117 8
118 9
119 9
120 9
121 9
122 9
123 9
124 9
125 9
126 10
127 9
128 10
129 9
130 10
131 9
132 10
133 10
134 10
135 10
136 10
137 10
138 10
139 10
140 11
141 10
142 11
143 10
144 11
145 10
146 11
147 11
148 11
149 11
150 11
151 11
152 11
153 11
154 12
155 11
156 12
157 11
158 12
159 11
160 12
161 12
162 12
163 12
164 12
165 12
166 12
167 12
168 13
169 12
170 13
171 12
172 13
173 12
174 13
175 13
176 13
177 13
178 13
179 13
180 13
181 13
182 14
183 13
184 14
185 13
186 14
187 13
188 14
189 14
190 14
191 14
192 14
193 14
194 14
195 14
196 15
197 14
198 15
199 14
200 15
201 14
202 15
203 15
204 15
205 15
206 15
207 15
208 15
209 15
210 16
211 15
212 16
213 15
214 16
215 15
216 16
217 16
218 16
219 16
220 16
221 16
222 16
223 16
224 17
225 16
226 17
227 16
228 17
229 16
230 17
231 17
232 17
233 17
234 17
235 17
236 17
237 17
238 18
239 17
240 18
241 17
242 18
243 17
244 18
245 18
246 18
247 18
248 18
249 18
250 18
251 18
252 19
253 18
254 19
255 18
256 19
257 18
258 19
259 19
260 19
261 19
262 19
263 19
264 19
265 19
266 20
267 19
268 20
269 19
270 20
271 19
272 20
273 20
274 20
275 20
276 20
277 20
278 20
279 20
280 21
281 20
282 21
283 20
284 21
285 20
286 21
287 21
288 21
289 21
290 21
291 21
292 21
293 21
294 22
295 21
296 22
297 21
298 22
299 21
300 22
301 22
302 22
303 22
304 22
305 22
306 22
307 22
308 23
309 22
310 23
311 22
312 23
313 22
314 23
315 23
316 23
317 23
318 23
319 23
320 23
321 23
322 24
323 23
324 24
325 23
326 24
327 23
328 24
329 24
330 24
331 24
332 24
333 24
334 24
335 24
336 25
337 24
338 25
339 24
340 25
341 24
342 25
343 25
344 25
345 25
346 25
347 25
348 25
349 25
350 26
351 25
352 26
353 25
354 26
355 25
356 26
357 26
358 26
359 26
360 26
361 26
362 26
363 26
364 27
365 26
366 27
367 26
368 27
369 26
370 27
371 27
372 27
373 27
374 27
375 27
376 27
377 27
378 28
379 27
380 28
381 27
382 28
383 27
384 28
385 28
386 28
387 28
388 28
389 28
390 28
391 28
392 29
393 28
394 29
395 28
396 29
397 28
398 29
399 29
400 29
401 29
402 29
403 29
404 29
405 29
406 30
407 29
408 30
409 29
410 30
411 29
412 30
413 30
414 30
415 30
416 30
417 30
418 30
419 30
420 31
421 30
422 31
423 30
424 31
425 30
426 31
427 31
428 31
429 31
430 31
431 31
432 31
433 31
434 32
435 31
436 32
437 31
438 32
439 31
440 32
441 32
442 32
443 32
444 32
445 32
446 32
447 32
448 33
449 32
450 33
451 32
452 33
453 32
454 33
455 33
456 33
457 33
458 33
459 33
460 33
461 33
462 34
463 33
464 34
465 33
466 34
467 33
468 34
469 34
470 34
471 34
472 34
473 34
474 34
475 34
476 35
477 34
478 35
479 34
480 35
481 34
482 35
483 35
484 35
485 35
486 35
487 35
488 35
489 35
490 36
491 35
492 36
493 35
494 36
495 35
496 36
497 36
498 36
499 36
500 36
501 36
502 36
503 36
504 37
505 36
506 37
507 36
508 37
509 36
510 37
511 37
512 37
513 37
514 37
515 37
516 37
517 37
518 38
519 37
520 38
521 37
522 38
523 37
524 38
525 38
526 38
527 38
528 38
529 38
530 38
531 38
532 39
533 38
534 39
535 38
536 39
537 38
538 39
539 39
540 39
541 39
542 39
543 39
544 39
545 39
546 40
547 39
548 40
549 39
550 40
551 39
552 40
553 40
554 40
555 40
556 40
557 40
558 40
559 40
560 41
561 40
562 41
563 40
564 41
565 40
566 41
567 41
568 41
569 41
570 41
571 41
572 41
573 41
574 42
575 41
576 42
577 41
578 42
579 41
580 42
581 42
582 42
583 42
584 42
585 42
586 42
587 42
588 43
589 42
590 43
591 42
592 43
593 42
594 43
595 43
596 43
597 43
598 43
599 43
600 43
601 43
602 44
603 43
604 44
605 43
606 44
607 43
608 44
609 44
610 44
611 44
612 44
613 44
614 44
615 44
616 45
617 44
618 45
619 44
620 45
621 44
622 45
623 45
624 45
625 45
626 45
627 45
628 45
629 45
630 46
631 45
632 46
633 45
634 46
635 45
636 46
637 46
638 46
639 46
640 46
641 46
642 46
643 46
644 47
645 46
646 47
647 46
648 47
649 46
650 47
651 47
652 47
653 47
654 47
655 47
656 47
657 47
658 48
659 47
660 48
661 47
662 48
663 47
664 48
665 48
666 48
667 48
668 48
669 48
670 48
671 48
672 49
673 48
674 49
675 48
676 49
677 48
678 49
679 49
680 49
681 49
682 49
683 49
684 49
685 49
686 50
687 49
688 50
689 49
690 50
691 49
692 50
693 50
694 50
695 50
696 50
697 50
698 50
699 50
700 51
701 50
702 51
703 50
704 51
705 50
706 51
707 51
708 51
709 51
710 51
711 51
712 51
713 51
714 52
715 51
716 52
717 51
718 52
719 51
720 52
721 52
722 52
723 52
724 52
725 52
726 52
727 52
728 53
729 52
730 53
731 52
732 53
733 52
734 53
735 53
736 53
737 53
738 53
739 53
740 53
741 53
742 54
743 53
744 54
745 53
746 54
747 53
748 54
749 54
750 54
751 54
752 54
753 54
754 54
755 54
756 55
757 54
758 55
759 54
760 55
761 54
762 55
763 55
764 55
765 55
766 55
767 55
768 55
769 55
770 56
771 55
772 56
773 55
774 56
775 55
776 56
777 56
778 56
779 56
780 56
781 56
782 56
783 56
784 57
785 56
786 57
787 56
788 57
789 56
790 57
791 57
792 57
793 57
794 57
795 57
796 57
797 57
798 58
799 57
800 58
801 57
802 58
803 57
804 58
805 58
806 58
807 58
808 58
809 58
810 58
811 58
812 59
813 58
814 59
815 58
816 59
817 58
818 59
819 59
820 59
821 59
822 59
823 59
824 59
825 59
826 60
827 59
828 60
829 59
830 60
831 59
832 60
833 60
834 60
835 60
836 60
837 60
838 60
839 60
840 61
841 60
842 61
843 60
844 61
845 60
846 61
847 61
848 61
849 61
850 61
851 61
852 61
853 61
854 62
855 61
856 62
857 61
858 62
859 61
860 62
861 62
862 62
863 62
864 62
865 62
866 62
867 62
868 63
869 62
870 63
871 62
872 63
873 62
874 63
875 63
876 63
877 63
878 63
879 63
880 63
881 63
882 64
883 63
884 64
885 63
886 64
887 63
888 64
889 64
890 64
891 64
892 64
893 64
894 64
895 64
896 65
897 64
898 65
899 64
900 65
901 64
902 65
903 65
904 65
905 65
906 65
907 65
908 65
909 65
910 66
911 65
912 66
913 65
914 66
915 65
916 66
917 66
918 66
919 66
920 66
921 66
922 66
923 66
924 67
925 66
926 67
927 66
928 67
929 66
930 67
931 67
932 67
933 67
934 67
935 67
936 67
937 67
938 68
939 67
940 68
941 67
942 68
943 67
944 68
945 68
946 68
947 68
948 68
949 68
950 68
951 68
952 69
953 68
954 69
955 68
956 69
957 68
958 69
959 69
960 69
961 69
962 69
963 69
964 69
965 69
966 70
967 69
968 70
969 69
970 70
971 69
972 70
973 70
974 70
975 70
976 70
977 70
978 70
979 70
980 71
981 70
982 71
983 70
984 71
985 70
986 71
987 71
988 71
989 71
990 71
991 71
992 71
993 71
994 72
995 71
996 72
997 71
998 72
999 71
1000 72