1000
684 154 28
3 772 333168
655 373 49
986 634 1
596 194 774375
909 158 1
50 745 1
409 282 1
958 709 1
807 936 1
863 550 32
468 634 1
277 250 1
351 987 1018511
483 90 1
107 295 550486
148 789 1
835 109 43
486 861 1
642 977 1
123 96 136466
561 218 1080008
219 1 1
162 4 1
288 709 1
680 728 1
249 278 1
594 283 1
666 160 1
148 424 56
665 489 8
915 111 585230
219 875 1
239 554 319267
387 159 1
472 152 1
121 360 590805
882 274 1
513 86 1
803 469 94
68 606 28
154 471 28
792 644 1
792 914 44
805 427 600997
512 253 1
746 309 1
548 638 172484
990 721 1
225 80 320578
883 406 899571
132 747 45
263 290 84
600 174 1
631 200 70
849 937 512067
511 563 1
348 899 194247
495 979 952692
108 932 1
980 66 1095643
860 770 1
82 226 1
965 480 6
643 770 1
644 913 1
371 65 1
867 65 1
307 381 29
964 271 537055
362 439 17
796 314 1
289 408 761515
482 468 17
702 911 1
202 554 149453
963 479 1
904 119 1
948 314 9
546 391 31
323 295 952014
589 428 1
555 348 1
12 791 1
256 585 1
591 860 1
313 753 1
700 636 1
768 974 8
840 626 48
612 357 1
51 845 1
360 937 696027
567 101 1
529 773 1
335 909 1
863 215 1
607 455 1
950 247 751278
203 819 44
261 871 999743
718 589 1
732 624 69
52 188 966296
395 357 1
798 563 6
47 248 1
231 230 1
417 686 1
66 55 714612
1000 978 1
953 312 1
648 418 88
889 28 31
542 270 1
832 538 2
206 895 1
82 769 27
925 492 1
719 226 19
8 814 1
395 211 1
205 660 1
776 358 1
292 159 1
981 83 1
821 724 1
185 775 1
470 290 1
927 701 4
828 450 572027
294 427 159330
989 248 1
881 570 223394
172 820 818074
44 132 1
305 935 2
646 386 1051836
453 955 54
480 667 1
577 720 1
430 534 1
366 105 784027
984 985 1
47 627 1
641 664 908661
866 181 1
35 312 1
992 627 1
166 183 613882
56 349 24
31 646 864700
259 703 1
496 483 1
658 735 15
198 40 184937
389 288 80
629 432 1
492 731 1
692 666 18
218 711 1
464 940 1
381 680 1
777 511 1
251 658 1
269 815 1032243
481 539 1
557 638 776908
6 595 1
176 879 1
633 662 30
737 883 558711
606 771 1
934 187 1
591 199 5
104 378 10
15 945 407123
695 444 4
191 788 1
776 99 15
1000 606 1
730 771 29
124 337 487278
784 513 1
792 420 1
272 43 1080446
876 106 453355
710 81 160290
152 162 1
297 540 1
392 610 4
56 264 1
745 908 101
514 522 61
155 697 816470
236 705 471746
717 215 1
374 466 1
17 765 622561
144 305 1
156 549 681784
873 165 700473
940 400 1
189 117 69
889 375 1
127 182 1
738 21 60
966 536 893288
829 279 626990
561 308 341247
18 103 1
746 13 3
716 400 1
890 260 10
18 867 1
278 847 1
256 391 1
331 200 1
5 14 1045204
268 431 990778
928 344 1
299 611 92
351 347 376268
699 801 779909
173 340 1
813 570 1
773 598 419975
991 830 1
703 130 353457
384 635 1
943 700 1
912 501 1
317 151 188181
337 752 736367
988 130 556275
702 34 57
63 163 2
855 208 1
564 885 33
720 862 1
741 791 1
535 755 1
967 384 1
441 952 740740
790 17 861838
755 808 318728
176 156 945951
828 551 155521
15 817 284973
166 999 949076
367 371 1
484 781 21
178 498 1
732 449 69
566 841 1
54 560 1
436 682 12
940 676 24
815 849 107809
388 751 83
419 245 692238
939 768 1
353 775 63
652 973 1
774 803 1
653 587 1
510 181 1
10 63 1
651 435 528021
980 155 363370
27 924 6
528 56 1
904 599 43
341 810 19
999 310 839286
851 746 1
125 839 1
376 35 1
191 622 14
647 858 44
628 873 1
952 272 732468
72 938 1
574 748 1
746 276 16
869 149 150416
390 88 9
135 900 1
264 978 1
61 503 274857
112 802 271111
610 338 1
125 972 1
539 736 1
171 321 1
167 971 29
334 754 1
904 203 1
528 405 23
461 782 38
896 571 92
420 731 1
153 77 232681
328 431 581428
696 873 970840
731 794 42
380 567 2
795 859 1
95 234 9
751 958 1
826 972 1
243 939 9
372 241 358891
144 209 1
953 212 79
467 156 1
211 846 1
661 470 83
836 509 1
129 462 641933
234 643 1
24 662 1
696 128 604648
315 887 688993
512 363 1
486 962 1
952 244 1
767 280 1
38 58 34
900 44 1
859 160 1
916 882 1
672 539 1
191 621 79
383 280 51
381 793 29
410 942 452180
266 564 10
93 846 2
886 732 69
750 519 161678
629 868 1
226 809 1
369 475 1
604 521 49
280 626 1
807 892 22
966 812 989432
343 284 10
460 630 294314
818 742 24
564 421 33
211 990 1
536 988 806480
515 593 215427
104 132 1
594 173 1
931 430 1
144 993 3
682 716 1
724 924 1
928 823 600762
457 92 1
338 466 1
484 949 1
162 368 38
346 175 778788
603 838 254615
385 887 755973
218 242 1077052
859 356 1
803 87 1
653 494 1
517 689 1
623 791 7
922 830 1
401 115 1
126 484 1
594 57 42
476 880 62
103 689 1
991 444 1
472 157 1
771 587 1
972 324 8
358 787 1
911 214 74
226 285 28
664 136 716763
2 497 1
281 356 19
694 803 77
685 105 374430
439 656 1
574 800 1
721 842 1
66 161 1
496 311 71
713 359 1
193 540 1
922 364 1
512 356 1
89 164 606312
627 933 1
136 25 1
626 86 1
233 191 1
239 350 1028269
448 446 570638
409 53 1
697 852 803623
128 843 511294
294 982 863227
817 195 1
64 189 69
234 497 1
532 277 24
805 14 996457
672 704 1
443 801 726815
116 320 1
250 818 1
461 411 1
40 531 386933
148 572 1
674 376 76
428 832 1
32 660 32
975 542 662219
548 414 374561
920 229 1
224 354 1
722 298 1
382 249 38
464 53 1
767 6 1
876 328 877393
765 450 858179
331 673 25
946 178 24
425 583 29
252 986 19
625 42 1
806 693 30
491 181 52
204 788 80
373 104 1
976 86 49
609 572 1
857 227 48
832 379 1
507 825 1
576 904 25
326 465 1067538
381 712 29
288 953 1
944 680 28
983 986 19
606 210 9
220 600 1
193 147 32
91 203 44
291 350 691974
690 895 818547
122 632 1
297 169 1
291 134 659360
48 911 74
838 412 763443
902 884 1
251 474 14
205 38 1
637 130 1
242 596 704898
797 490 1
905 640 30
317 930 1
477 237 7
320 706 25
284 319 1
103 62 5
273 293 1
37 197 1
699 515 125294
197 559 16
262 876 1
78 141 1
686 558 1
253 223 1
531 213 318558
59 333 1
728 525 27
71 766 106143
997 855 1
179 690 432273
113 710 671323
426 115 104
734 301 1
194 393 386548
996 55 1
402 432 1
718 352 1
583 16 1
443 871 491229
372 347 963355
1 884 1
848 952 1
552 814 1
603 289 915518
361 340 1
778 521 1
330 939 6
310 315 941112
10 216 3
20 986 19
602 416 1
663 178 24
868 334 1
734 581 905292
429 649 231204
808 96 372692
188 920 747460
940 322 24
785 494 32
788 607 1
533 911 1
691 847 1
84 273 1
473 982 187893
697 192 1
932 523 259797
573 56 24
660 24 1
795 274 1
455 901 47
977 753 1
672 72 1
777 30 4
651 500 1033787
924 698 14
601 305 2
761 490 1
459 6 53
593 877 591324
667 231 1
500 465 1075786
169 472 1
723 196 1
312 671 59
740 615 340561
233 963 1
762 484 21
87 896 1
875 251 1
488 475 1
766 396 1076308
822 777 1
969 820 1
76 683 409701
668 415 1
632 373 1
530 812 280708
729 852 352802
416 665 1
751 196 1
519 877 976990
783 921 59
36 224 1
903 5 318082
435 834 223129
232 104 50
207 723 85
124 549 1084410
85 423 7
468 208 1
441 222 405012
36 115 1
83 413 1
47 139 2
122 913 1
323 394 613939
776 659 15
857 585 1
458 131 643071
423 665 1
534 851 1
809 806 1
341 656 1
517 255 1
119 577 1
564 438 1
891 193 1
21 954 1
619 856 806250
258 902 1
927 10 1
422 503 1
472 917 36
678 741 1
668 579 86
79 934 903280
228 768 8
384 846 1
740 757 652350
764 222 534606
485 410 113452
878 226 28
327 409 20
756 975 517760
168 774 1
6 73 53
495 757 104247
326 308 953051
617 678 5
954 158 1
804 984 159119
598 342 1
451 629 73
733 648 1
839 970 1
231 454 14
317 269 905600
649 987 962056
831 151 319308
47 707 2
880 313 1
332 910 217754
759 961 1
528 949 1
977 180 65
846 70 2
39 357 1
565 861 64
581 235 717167
925 4 1
773 504 814981
826 527 1
825 375 1
278 837 37
487 776 1
149 750 316272
92 126 1
101 841 1
189 827 69
981 916 1
586 817 1
445 89 1068022
267 915 777373
910 346 730957
537 638 1
923 910 1
438 169 1
448 756 569485
518 140 284354
260 174 1
820 386 859289
282 341 1
811 16 28
867 995 3
681 354 807727
972 499 8
841 998 1
76 170 175750
708 123 978618
926 414 954505
800 562 1
225 790 661321
369 217 1
683 69 716462
595 303 1
145 494 1
763 171 1
118 867 3
41 713 18
77 755 432212
553 547 38
345 168 1
50 636 1
97 87 48
643 605 5
830 556 1
822 387 1
924 37 1
415 648 1
843 406 178861
501 611 1
797 428 1
775 141 1
726 931 1
153 934 1096916
402 479 1
111 131 605712
505 972 8
932 332 876623
510 453 1
446 580 1034291
460 348 208487
547 862 1
377 912 1
496 237 1
201 329 566465
198 551 1038402
179 508 537091
583 905 1
247 202 628498
558 927 1
261 355 1
313 670 63
203 391 1
619 881 276716
654 618 257042
783 733 1
960 610 17
588 106 134174
818 526 26
918 169 35
462 618 898370
234 725 9
434 678 5
221 145 1
907 789 55
832 127 1
221 575 34
318 705 111313
880 109 1
668 853 86
905 891 1
786 217 1
791 398 1
429 452 529391
641 865 507506
734 55 996581
253 339 17
258 417 1
296 416 9
765 67 1
88 255 1
66 190 1
926 140 484288
864 669 531502
413 154 1
125 321 1
203 657 44
335 303 1
468 578 17
356 22 19
759 642 1
298 480 1
151 715 1
470 455 1
359 370 1
320 178 1
59 442 36
869 397 400605
896 230 1
277 748 1
223 658 1
564 863 1
509 804 371492
354 407 107
47 567 1
942 749 626198
816 911 31
452 764 779437
254 842 1
844 563 1
754 732 1
973 88 1
189 293 1
391 677 45
23 745 1
971 154 1
722 959 1
374 220 1
286 533 75
590 938 1
9 943 1
152 545 22
737 625 896363
268 687 1096865
264 150 25
46 611 92
789 316 26
872 689 6
16 682 1
654 516 386419
82 116 1
26 780 46
371 760 1
610 666 1
799 688 660544
678 444 1
702 237 1
897 754 70
100 59 1
146 109 1
361 249 1
749 142 1054485
182 970 1
119 727 42
568 114 68
957 894 1
53 870 22
584 688 1
951 689 6
453 488 1
44 33 52
114 732 1
685 102 1
100 547 1
142 287 692531
685 508 669607
29 493 1085826
943 403 97
170 947 98
83 11 18
461 78 1
560 609 1
850 98 114454
569 796 10
784 780 1
45 788 80
783 824 1
763 478 12
802 580 196702
506 560 59
213 557 882281
175 419 961350
824 611 1
98 485 193246
391 779 45
889 806 1
457 614 18
200 189 1
157 507 1
110 530 997979
679 815 1
84 94 1
570 81 832571
237 75 72
893 152 37
215 463 16
602 941 1
986 919 19
814 945 629972
293 743 68
176 984 1008894
69 687 818712
931 652 1
428 906 3
668 723 1
496 184 71
504 895 967828
164 541 109406
306 763 1
956 941 1
560 433 59
544 334 71
772 688 749769
726 796 1
82 592 27
287 834 717054
31 817 279267
522 21 1
186 319 1
300 844 5
874 325 1083780
821 2 1
680 74 28
929 6 53
136 703 412411
377 9 1
381 717 1
845 305 1
509 799 1089790
591 209 1
7 858 1
741 898 6
832 650 4
957 63 1
3 165 1018694
968 899 966888
71 714 1
829 823 383513
997 675 1
71 267 456379
962 522 1
986 562 1
998 423 1
854 54 1
256 177 46
865 172 270502
414 833 1
950 366 917877
814 43 478932
866 778 1
80 121 915724
961 90 1
345 170 1
708 518 295742
613 807 22
807 498 1
615 107 747706
864 302 1
523 542 706773
861 94 1
968 385 817408
23 401 1
240 732 69
282 137 5
832 447 4
61 458 890971
49 636 99
365 423 7
826 456 7
237 331 1
246 131 1
648 275 88
971 662 1
520 913 46
786 146 1
112 79 430570
787 713 1
844 186 1
744 278 37
284 941 1
625 681 831518
440 891 31
257 357 1
336 841 5
60 590 1
527 590 1
903 588 991224
159 620 1
457 309 1
114 411 1
197 439 1
521 857 1
236 279 323056
113 29 1068911
158 120 58
964 864 1091475
818 728 1
143 239 1
10 639 3
542 304 1
261 669 924134
888 954 59
135 789 1
487 306 1
437 16 28
318 325 916139
780 7 1
314 12 1
543 600 12
201 752 609850
959 290 1
632 758 48
52 408 720401
260 939 1
399 162 38
825 265 33
501 608 93
493 241 331055
582 610 17
273 19 29
850 445 226992
739 574 22
329 134 399789
856 271 624391
956 675 1
516 235 1033953
412 473 336241
183 503 928109
402 138 75
133 146 60
533 376 1
502 428 1
729 630 826526
597 283 43
370 936 1
645 63 1
598 110 506861
854 185 1
858 283 1
831 396 1075717
129 393 134750
524 401 103
394 541 1049579
691 38 1
920 979 1023371
768 254 1
340 616 40
333 221 1
245 874 467140
928 397 886745
404 53 22
466 994 15
78 238 48