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