1 1
2 0
3 2 
4 5 
5 3 
6 37 
7 21 
8 29 
9 67 
10 71 
11 23 
12 11 
13 15 
14 7 
15 58 
16 12 
17 41 
18 8 
19 66 
20 25 
21 35 
22 370 
23 35 
24 17 
25 75 
26 159 
27 198 
28 30 
29 37 
30 153 
31 232 
32 333 
33 170 
34 507 
35 108 
36 279 
37 41 
38 61 
39 486 
40 9 
41 194 
42 211 
43 29 
44 73 
45 173 
46 575 
47 152 
48 214 
49 10 
50 147 
51 126 
52 672 
53 388 
54 77 
55 358 
56 1048 
57 528 
58 291 
59 322 
60 1491 
61 536 
62 173 
63 2055 
64 131 
65 526 
66 773 
67 573 
68 188 
69 195 
70 252 
71 417 
72 300 
73 851 
74 560 
75 419 
76 532 
77 923 
78 190 
79 1465 
80 56 
81 207 
82 560 
83 49 
84 217 
85 219 
86 226 
87 42 
88 633 
89 13 
90 411 
91 1736 
92 321 
93 131 
94 710 
95 438 
96 2375 
97 111 
98 196 
99 293 
100 149 
101 596 
102 14 
103 1933 
104 464 
105 1022 
106 276 
107 428 
108 260 
109 171 
110 495 
111 1938 
112 637 
113 457 
114 401 
115 1509 
116 418 
117 692 
118 78 
119 174 
120 573 
121 20 
122 903 
123 2068 
124 63 
125 309 
126 476 
127 668 
128 796 
129 328 
130 880 
131 87 
132 1730 
133 657 
134 582 
135 38 
136 166 
137 790 
138 125 
139 531 
140 43 
141 1185 
142 86 
143 655 
144 28 
145 7054 
146 608 
147 22 
148 95 
149 1502 
150 147 
151 880 
152 901 
153 650 
154 1964 
155 1239 
156 1709 
157 2098 
158 684 
159 940 
160 2608 
161 750 
162 443 
163 293 
164 208 
165 283 
166 242 
167 811 
168 1082 
169 2733 
170 64 
171 307 
172 106 
173 1680 
174 1150 
175 927 
176 1557 
177 812 
178 2335 
179 913 
180 408 
181 1104 
182 31 
183 656 
184 653 
185 60 
186 970 
187 917 
188 1513 
189 2662 
190 1964 
191 1435 
192 39 
193 3670 
194 318 
195 3060 
196 2116 
197 308 
198 1495 
199 1149 
200 2568 
201 412 
202 419 
203 169 
204 701 
205 105 
206 1499 
207 260 
208 2327 
209 1979 
210 1644 
211 107 
212 1505 
213 1267 
214 68 
215 1711 
216 2190 
217 181 
218 758 
219 798 
220 1955 
221 2445 
222 1193 
223 486 
224 825 
225 1828 
226 477 
227 679 
228 4050 
229 5293 
230 404 
231 801 
232 65 
233 1271 
234 3849 
235 163 
236 957 
237 72 
238 2054 
239 720 
240 905 
241 1355 
242 7834 
243 84 
244 2572 
245 4859 
246 1039 
247 3761 
248 2205 
249 3411 
250 113 
251 5419 
252 889 
253 946 
254 792 
255 806 
256 1324 
257 1578 
258 1331 
259 364 
260 623 
261 5914 
262 474 
263 3161 
264 627 
265 789 
266 3233 
267 2303 
268 3263 
269 6054 
270 523 
271 1091 
272 3507 
273 118 
274 3350 
275 2259 
276 4978 
277 2636 
278 292 
279 1027 
280 3847 
281 2924 
282 1041 
283 294 
284 2783 
285 2919 
286 2293 
287 568 
288 379 
289 2277 
290 3750 
291 552 
292 1432 
293 3284 
294 1549 
295 1131 
296 3145 
297 1074 
298 1059 
299 5294 
300 2721 
301 424 
302 374 
303 1697 
304 447 
305 729 
306 3559 
307 5368 
308 703 
309 541 
310 5466 
311 1466 
312 1657 
313 1505 
314 1108 
315 1322 
316 298 
317 3857 
318 2351 
319 5261 
320 820 
321 3116 
322 214 
323 671 
324 24 
325 2730 
326 2597 
327 240 
328 477 
329 2953 
330 1598 
331 2726 
332 2197 
333 3048 
334 2109 
335 1596 
336 144 
337 3615 
338 5117 
339 135 
340 1930 
341 8092 
342 2853 
343 552 
344 297 
345 271 
346 1399 
347 4878 
348 3951 
349 8867 
350 3257 
351 2071 
352 3923 
353 2858 
354 62 
355 4214 
356 1071 
357 2448 
358 595 
359 3344 
360 2218 
361 431 
362 873 
363 155 
364 3786 
365 1400 
366 5452 
367 819 
368 708 
369 1220 
370 2603 
371 1410 
372 138 
373 7389 
374 2969 
375 873 
376 550 
377 438 
378 81 
379 333 
380 4186 
381 3233 
382 1124 
383 6166 
384 1820 
385 1088 
386 1843 
387 771 
388 1857 
389 811 
390 783 
391 3604 
392 26 
393 1991 
394 2635 
395 3086 
396 7300 
397 4936 
398 981 
399 7979 
400 2426 
401 5846 
402 877 
403 1273 
404 280 
405 1639 
406 966 
407 646 
408 969 
409 3644 
410 1304 
411 94 
412 6282 
413 3744 
414 1893 
415 2312 
416 246 
417 1526 
418 1222 
419 7112 
420 85 
421 3285 
422 2580 
423 168 
424 3986 
425 1718 
426 27 
427 4326 
428 1091 
429 1379 
430 514 
431 1364 
432 1203 
433 8952 
434 2830 
435 250 
436 3374 
437 8212 
438 2023 
439 1762 
440 1260 
441 2506 
442 261 
443 3721 
444 137 
445 5340 
446 2317 
447 1043 
448 521 
449 9106 
450 2027 
451 671 
452 4008 
453 944 
454 1647 
455 5875 
456 2699 
457 3659 
458 380 
459 833 
460 2820 
461 10080 
462 1048 
463 1456 
464 3866 
465 10015 
466 740 
467 1127 
468 3808 
469 1127 
470 2093 
471 1659 
472 3792 
473 3082 
474 6698 
475 2753 
476 6519 
477 4088 
478 177 
479 736 
480 4077 
481 2080 
482 287 
483 3070 
484 4090 
485 569 
486 3627 
487 6677 
488 249 
489 1568 
490 9955 
491 5046 
492 9656 
493 3133 
494 2778 
495 3277 
496 1663 
497 687 
498 10029 
499 2341 
500 1789 
501 650 
502 5447 
503 8933 
504 291 
505 269 
506 4792 
507 2340 
508 1318 
509 1536 
510 2882 
511 1099 
512 3241 
513 4242 
514 54 
515 8692 
516 3072 
517 703 
518 1534 
519 6769 
520 2269 
521 7795 
522 1028 
523 6036 
524 1793 
525 7872 
526 901 
527 1985 
528 1265 
529 2227 
530 1014 
531 2665 
532 5336 
533 1064 
534 1292 
535 2340 
536 5663 
537 10024 
538 8200 
539 3980 
540 468 
541 1349 
542 3625 
543 1168 
544 3294 
545 4836 
546 290 
547 278 
548 1407 
549 132 
550 664 
551 8340 
552 953 
553 1489 
554 666 
555 4307 
556 916 
557 1753 
558 729 
559 2211 
560 9135 
561 539 
562 428 
563 2068 
564 1572 
565 1181 
566 1725 
567 8452 
568 2443 
569 9171 
570 52 
571 8382 
572 968 
573 2886 
574 5309 
575 2215 
576 5614 
577 6676 
578 6275 
579 5621 
580 1318 
581 10085 
582 1895 
583 1520 
584 1638 
585 5581 
586 199 
587 4333 
588 3003 
589 5734 
590 145 
591 529 
592 1947 
593 405 
594 10235 
595 7226 
596 5859 
597 1182 
598 746 
599 4509 
600 232 
601 4576 
602 6053 
603 1701 
604 3147 
605 2579 
606 311 
607 98 
608 1172 
609 348 
610 4058 
611 4813 
612 10224 
613 2307 
614 8641 
615 4761 
616 4501 
617 750 
618 3638 
619 8575 
620 4277 
621 2905 
622 3537 
623 5821 
624 1617 
625 5640 
626 4509 
627 7164 
628 411 
629 6156 
630 1437 
631 6356 
632 5224 
633 55 
634 1879 
635 9851 
636 3016 
637 1118 
638 1132 
639 256 
640 2082 
641 679 
642 5322 
643 7729 
644 3065 
645 2153 
646 74 
647 637 
648 5001 
649 8394 
650 9633 
651 4790 
652 1137 
653 2896 
654 1225 
655 3875 
656 5756 
657 7123 
658 8221 
659 9790 
660 4799 
661 3604 
662 5416 
663 10076 
664 1428 
665 2875 
666 4030 
667 33 
668 161 
669 5078 
670 507 
671 1816 
672 8679 
673 9743 
674 7319 
675 496 
676 2291 
677 6105 
678 1176 
679 2448 
680 2770 
681 4514 
682 588 
683 2506 
684 179 
685 1115 
686 2142 
687 8125 
688 2884 
689 4056 
690 3539 
691 4318 
692 6324 
693 1262 
694 1170 
695 3325 
696 5742 
697 5693 
698 8371 
699 772 
700 2880 
701 9919 
702 8405 
703 6732 
704 3952 
705 44 
706 2450 
707 5569 
708 1998 
709 3659 
710 1778 
711 5266 
712 3613 
713 762 
714 2404 
715 1547 
716 7918 
717 930 
718 140 
719 7269 
720 4832 
721 367 
722 1250 
723 2816 
724 9037 
725 2450 
726 3997 
727 1171 
728 4382 
729 8287 
730 2679 
731 4266 
732 1835 
733 5118 
734 4303 
735 5871 
736 7123 
737 343 
738 3901 
739 4098 
740 2230 
741 421 
742 5354 
743 743 
744 9369 
745 636 
746 1043 
747 1549 
748 1534 
749 676 
750 4419 
751 2307 
752 386 
753 3215 
754 8187 
755 8720 
756 2876 
757 3250 
758 3956 
759 6555 
760 8285 
761 701 
762 9866 
763 1536 
764 2164 
765 3842 
766 4865 
767 4468 
768 2518 
769 1447 
770 3653 
771 506 
772 2173 
773 817 
774 377 
775 2719 
776 4206 
777 5800 
778 2322 
779 8321 
780 1004 
781 93 
782 4683 
783 1306 
784 2751 
785 4715 
786 1826 
787 6386 
788 10002 
789 1310 
790 6031 
791 5225 
792 6932 
793 9626 
794 3809 
795 2136 
796 9659 
797 5296 
798 1389 
799 3093 
800 5608 
801 9640 
802 2756 
803 5396 
804 1654 
805 2163 
806 608 
807 8681 
808 36 
809 8336 
810 1963 
811 4128 
812 1874 
813 1660 
814 3036 
815 6927 
816 1381 
817 6816 
818 5563 
819 9110 
820 8016 
821 1140 
822 2641 
823 5767 
824 2363 
825 911 
826 5446 
827 1243 
828 4088 
829 705 
830 2394 
831 1249 
832 7737 
833 3339 
834 1803 
835 1419 
836 6442 
837 2871 
838 3551 
839 1885 
840 3207 
841 3973 
842 8623 
843 2366 
844 396 
845 2843 
846 1827 
847 9743 
848 127 
849 3863 
850 8312 
851 3260 
852 979 
853 5860 
854 1631 
855 886 
856 3816 
857 8028 
858 6288 
859 9508 
860 2929 
861 9724 
862 2758 
863 831 
864 9232 
865 9425 
866 6288 
867 3996 
868 2249 
869 3732 
870 7683 
871 1921 
872 5266 
873 8609 
874 5125 
875 2379 
876 7199 
877 6632 
878 2403 
879 4052 
880 1309 
881 3940 
882 509 
883 1894 
884 2648 
885 7544 
886 6361 
887 5237 
888 1748 
889 1728 
890 1139 
891 10127 
892 7998 
893 2883 
894 846 
895 1265 
896 4798 
897 5517 
898 1896 
899 6705 
900 4334 
901 245 
902 2847 
903 2570 
904 3388 
905 8615 
906 6958 
907 50 
908 1526 
909 2501 
910 2664 
911 3374 
912 1731 
913 3890 
914 2616 
915 5747 
916 5843 
917 6974 
918 9319 
919 7007 
920 686 
921 3101 
922 3410 
923 1320 
924 2740 
925 5782 
926 3166 
927 2343 
928 9265 
929 4367 
930 1684 
931 2164 
932 683 
933 3839 
934 314 
935 2025 
936 778 
937 51 
938 388 
939 5822 
940 2327 
941 254 
942 3176 
943 392 
944 6982 
945 889 
946 557 
947 7511 
948 6777 
949 828 
950 5889 
951 7628 
952 4188 
953 6553 
954 4687 
955 7239 
956 324 
957 286 
958 3954 
959 4118 
960 7740 
961 406 
962 7437 
963 1167 
964 3303 
965 635 
966 6021 
967 6747 
968 626 
969 3272 
970 9119 
971 5825 
972 977 
973 3115 
974 4063 
975 2926 
976 4962 
977 4098 
978 6088 
979 3785 
980 3610 
981 2695 
982 1042 
983 3658 
984 7930 
985 2534 
986 1053 
987 1699 
988 6798 
989 70 
990 6808 
991 657 
992 3473 
993 3799 
994 1707 
995 1789 
996 809 
997 641 
998 7706 
999 7943 
1000 9172