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