1000000 500
539665 741410 2996747
47954 671526 1255349
488010 814796 1786361
352519 942745 105596
314817 393197 3600586
335684 591574 3633771
60918 324182 1340238
738864 740497 3501160
787289 941053 3266452
20861 236978 1210074
181648 532442 2061068
304323 375524 3342460
993789 994050 822548
477172 596597 3037131
886747 919784 3928443
587687 764451 2125625
961191 990224 974588
944152 986258 3238409
768653 813277 3811217
570471 758206 2782195
649731 700673 3390080
92672 239774 3053309
298782 489258 2246600
983958 984102 3687855
70413 91928 2693638
261395 266303 3146238
941109 944299 568836
989160 991536 374028
974862 978831 3657198
970853 989249 1650753
670786 755014 2820696
970412 990771 850019
92623 266992 1832920
276445 378928 2239338
811599 878233 3465395
396395 992838 38622
271637 494379 2152871
963262 970047 3497988
91511 266663 1466567
976566 981010 3619183
115196 251606 3005393
788729 854440 3666600
524873 733141 3011825
782299 910615 3394008
18513 47459 2764743
392455 721552 3012008
999719 999882 2462818
623429 699506 3067809
978451 986456 3334310
11370 600767 805354
996579 999588 445396
992100 993397 3681852
951919 952824 3962791
666490 720137 3287752
67406 67867 2509691
57821 817100 1338890
563257 594986 3940529
350551 400636 3844590
642968 643151 3719472
5302 749530 211305
63557 708358 1410447
665053 714311 3806159
803577 842026 3859808
942617 980172 1061376
993802 994374 85131
994235 998242 2669130
947180 987003 2851712
780699 784488 3853401
999447 999677 3696511
404713 466505 3912109
989606 990651 925662
469181 764987 1828056
987980 989133 2633654
943135 965717 1736641
180378 229789 3952508
300761 461247 3081326
163634 220485 3750755
325619 763065 2671053
663198 675453 3695107
997818 998180 3537529
893172 926155 3476000
980826 988222 2188280
997157 999321 3235220
959532 991790 181215
963646 984515 3368043
910722 919397 3968553
390749 457782 3991528
145474 165044 3845384
999414 999442 1375153
973585 974467 3826224
146636 249946 3464873
17274 43524 2083161
625964 653921 3419764
930458 934602 3483381
994161 997099 2679705
615840 764657 2107721
217244 261644 2977770
941071 941774 834630
964919 977336 3403135
353104 520988 3723916
962091 966560 3854469
870415 884384 3458750
57154 502053 1294381
566993 595949 3615117
483861 545156 3969372
636279 639941 3814218
834769 843341 3787571
836957 839107 3909569
851193 871188 3979673
999536 999861 594885
109518 126708 3218097
171153 202161 3957298
952208 987917 2201139
607523 612183 3242827
313726 413435 3453350
290645 297158 2267888
63870 71676 2203354
999100 999362 1372166
949665 985030 3361774
299601 717313 2625429
909070 939022 3303268
302826 543499 3119707
303444 542987 3251385
17109 485686 987755
962706 968928 3733106
748499 749600 3397531
943263 960478 2269143
742120 748514 3202600
678100 766620 1825380
545730 564703 3965893
874162 879762 3600184
956254 962714 3525560
948959 959691 3400098
767139 799169 2358026
721860 739181 3080418
888419 925365 3785722
50960 375019 1266992
928249 938081 3313449
250150 254595 3501891
997914 998786 3850409
500803 510713 3981648
630853 637020 3496709
731436 732341 3383042
767614 843391 2462527
337171 465152 3688276
293423 297623 3718179
528132 553265 3783437
133486 225810 3694209
682471 705482 3858459
492342 746562 2890400
10380 690219 596767
943387 974254 2982700
625445 636796 3089619
437644 596413 3438517
972945 986527 3131740
92377 320071 1823266
283047 293115 2360563
141237 239949 3649340
5269 111499 208637
9329 335533 521236
886745 887356 3430046
949653 954211 3566417
835077 886734 3443166
401220 679217 3029105
12676 321662 956057
369883 392263 3957094
956418 969740 3528406
999858 999910 3582917
442947 472222 3893382
924982 929906 3387980
982394 983654 3916258
806138 837944 3938787
914303 920237 3872798
379 227950 185114
949764 953648 3791861
69543 91708 2714832
279685 287590 3128544
10989 691022 619234
270913 752352 2126271
959992 972576 3497294
999949 999977 2256400
937396 937410 3599224
344794 457728 3699392
759678 760990 3747976
8922 835259 483256
999477 999716 2656266
102122 134152 3148285
168676 219662 3945078
589675 595291 3776567
978982 989311 1444379
895671 922265 3800060
946664 976531 3351973
908812 917857 3954907
436631 473324 3742274
191589 269527 2153982
958689 991231 645706
829632 848600 3785297
990122 994835 33412
692628 715517 3729152
90074 90249 3560460
942738 965426 1736463
238565 266722 2870104
967053 989479 1295238
973185 974982 3719699
798410 808425 3928944
363086 389872 3951659
768342 836548 2513977
978643 980345 3863332
137923 141298 3735834
93800 124685 3256348
962235 966973 3917486
985404 986502 3187744
8455 377980 234971
576971 760743 2729795
916774 939793 3271811
957262 960831 3535390
999973 999980 2438588
685241 705815 3853555
625995 628250 3888208
977254 989840 1283149
599930 606438 3659835
277304 281047 3501491
997730 999344 2361823
516679 520775 3994330
629791 633928 3498071
999785 999984 1533505
237898 239646 3903218
768440 919659 2606446
387766 754972 2877244
275100 713116 2233516
129695 216268 3653078
999901 999940 3282291
818789 932332 3333616
17293 22086 2470225
958215 962007 3570579
955920 991240 603758
594088 603818 3033955
10317 929892 531401
233 910608 118747
68673 91488 2703258
987162 987349 3597763
22085 25387 2778139
656442 684401 3593810
361931 408829 3850964
789869 817411 3864724
299421 719373 2369397
281712 288979 3211481
167462 221334 3760841
943798 981965 3069832
722789 733530 3254351
993318 993431 2502555
973523 987485 2300407
431641 479095 3738036
128560 220705 3468013
975745 980931 3861996
823066 842668 3799819
676946 763524 2498896
12614 906435 827728
736810 739383 3314059
274297 274699 3151255
126453 127599 3488925
326816 392387 3620102
362693 472536 3782315
793012 795563 3957826
617953 652223 3055978
179621 214960 3965094
299759 581427 2816868
755855 756171 2827847
953442 964659 3523420
987480 987552 3337862
980970 983512 3594441
986559 986763 3254244
501305 532355 3974244
229382 242504 3468184
628729 630836 3499433
314422 542179 3515608
959334 969881 3593347
285509 292050 3513515
99528 103745 3991925
54390 336821 1276847
219010 242453 3499423
349566 369170 3727412
727025 727402 3804545
949621 953496 3448449
790492 872896 3600086
148006 151158 3906702
275596 282119 2653186
999422 999544 3909334
59958 60979 1923183
67803 91268 2691684
977730 977732 3996962
995927 996260 2866988
299243 584268 2355279
304987 308949 3833781
92050 434300 1524932
769057 770468 3849855
301316 302078 3188299
905134 908012 3964294
529786 764422 2321217
380616 764193 2408205
388235 461901 3976614
996399 997141 3627666
654234 688847 3430346
875785 877700 3603833
174348 238325 3755050
984124 986209 3353029
722580 727178 3312685
81006 81270 3543552
999932 999949 2639261
768459 855407 2708764
481371 510538 3772555
945634 945645 3243569
299911 763623 2480948
304605 394014 3450531
556099 764776 2070533
751170 752501 2954120
664464 711729 3851218
670221 695346 3865783
273033 763928 2153031
518699 543935 3986926
92646 206985 2531978
703543 720035 3344698
543444 762142 2719635
942735 948866 1691991
779664 807289 3812103
823865 935792 3318916
971795 987694 2212233
14269 291925 962540
899384 901504 3958870
363401 402984 3953572
951447 987189 2473297
953779 990054 1216611
960729 991794 68233
994128 994760 344020
981556 983040 3819570
338414 596189 3445273
964023 965228 3939887
604 1918 2561898
999411 999499 1333572
766964 900720 2007879
65944 77716 2318694
991756 991758 2734181
7462 101183 231944
299717 494496 2674158
975936 981082 3603005
834653 849417 3752115
990418 990425 3308705
421839 617528 3029390
759410 760471 3189642
610155 614426 3230195
999811 999843 3238546
304316 551300 3272929
995266 996219 3804276
983987 987092 2715870
990235 991425 403895
972290 972444 3850737
773341 783923 3966649
626605 634083 3469389
992456 992516 3852324
546158 761575 2725559
286775 288343 3706347
131606 213458 3694057
774279 871207 3614148
687841 689909 3972517
742069 744937 3670343
281351 282635 3535887
892458 920338 3823984
481451 528730 3916575
691959 716001 3498064
896194 899679 3938824
766979 883947 2153287
148346 161790 3928916
596651 602584 3480779
709920 715527 3707473
738620 738679 3986889
254541 255907 3156072
362617 422142 3862802
648874 649916 3739482
6512 726745 213843
805359 883510 3459805
941897 948955 963115
990037 990112 1294886
873120 882206 3526731
973707 974553 3827202
156551 266864 2395428
768648 915583 2963939
998492 999177 3306819
71938 72291 3559412
493727 534696 3969456
275253 283559 2635036
175939 218287 3960404
956736 986763 3000036
12975 714634 957438
133131 138609 3735586
254848 255783 3525069
851141 860454 3969596
724226 766903 1811035
258263 264094 3160146
715556 758723 2765429
734863 737971 3781941
993829 993909 2582770
988889 990901 783899
969174 969296 3948819
418682 758323 2778448
934240 935224 3397406
47732 49599 1925053
970074 970768 3670922
891172 891418 3933655
65738 67210 2517783
299461 732164 2372189
899556 906237 3940500
64003 66752 3742344
385721 446825 3994468
83788 84697 3550958
659970 685596 3676571
129085 132031 3469477
971448 972260 3507360
882390 882454 3622348
988227 988940 3464081
680459 710035 3851357
945366 945481 3782424
12029 783367 826837
250752 250985 3523151
505345 513139 3992204
12626 751166 845779
113936 119441 3988349
689605 690086 3986361
941463 941821 1507697
947443 989273 1523465
181133 208950 3966560
889814 890806 3964268
92246 782881 1747320
625479 762994 2679760
450495 469834 3902498
999572 999631 3702901
659310 701580 3609438
287500 292126 3193875
403879 465823 3916155
346480 741589 2969092
92227 498059 1738361
949061 986487 3330538
731196 732020 3339957
62870 63311 3542504
72982 82475 3508267
972962 979472 3520034
399206 513328 3154455
889877 956194 480926
871089 959848 2333633
51102 453680 3414670
613140 954622 449579
136114 368821 232394
342714 450461 3484968
125086 680118 2984691
331340 501910 1601620
717318 920937 3216285
829518 943249 1400391
440683 634247 350746
844342 989041 23540
962848 989683 1480035
103612 243077 236931
717071 973716 2798580
129964 583700 3804804
616428 854586 2110493
375312 829308 3927354
580641 955812 942843
343804 394743 2211080
649373 986448 2441348
142697 575149 3769420
444126 482527 996934
998174 999726 1287304
155568 326039 2174517
501361 648606 2157137
278749 821426 2611764
311905 934526 1001108
888406 960466 1537320
714290 907552 3945909
495750 810501 1211335
143283 814558 3151935
765082 799610 3075807
138273 658130 1156049
155984 328722 1165457
458806 529520 3981716
794300 946450 1010702
403823 972810 1424434
944210 963785 3296965
604509 955626 2835169
44132 373201 945044
296225 467976 3409812
56053 758948 873213
600028 603296 1313741
883221 973983 1374240
874695 938540 2545037
301899 965342 631040
554530 579496 1024483
702689 754337 2228149
652450 982953 1754130
705702 983338 65679
10043 116216 768390
606966 760462 2658474
843821 963528 914197