1000 4
31123 1412686 2568727 3522037 4720301 5983678 6493911 7409417 8961234 9697821 10605233 11721975 12460191 13541274 14537622 15765405 16131561 17346286 18620148 19353600 20057109 21822564 22078321 23914741 24290552 25505574 26106214 27349455 28607152 29493386 30591454 31897736 32385346 33163740 34738383 35841266 36408054 37004396 38552537 39453726 40590257 41118810 42472957 43353422 44798929 45079521 46770463 47237208 48499406 49363810 50770367 51042011 52977296 53725938 54008309 55170279 56452364 57393957 58434540 59513127 60267043 61298844 62130273 63112209 64442172 65855884 66558811 67162705 68978401 69332752 70364461 71098737 72869144 73086833 74121131 75873805 76227331 77165684 78828073 79595702 80196858 81191973 82990075 83784548 84100520 85994274 86079592 87453793 88847268 89298665 90923248 91897587 92895249 93581350 94555840 95114634 96735865 97586551 98485236 99857898 100523685 101116866 102847309 103207322 104783616 105634489 106466355 107368077 108271660 109615915 110940908 111576015 112331173 113788366 114367838 115566132 116926038 117822411 118382210 119821117 120341369 121969034 122142570 123606732 124765043 125929215 126618933 127812746 128495855 129591669 130043024 131910422 132917307 133237913 134591151 135020463 136661984 137932937 138183501 139795429 140140933 141306974 142052449 143611132 144934086 145281974 146324641 147147490 148053842 149908743 150006395 151854355 152725123 153481696 154642642 155774729 156988289 157860225 158095351 159517289 160392345 161762142 162163432 163694316 164715162 165408110 166924173 167370826 168142321 169513338 170796145 171432109 172275846 173914020 174098494 175569748 176896214 177227318 178523388 179770310 180446675 181045036 182550924 183964409 184680761 185535427 186633568 187696771 188170802 189723330 190728318 191040256 192085485 193127369 194142709 195195716 196737787 197884058 198076254 199436419 200565610 201889508 202004311 203272574 204119590 205943511 206400252 207141616 208614541 209030500 210475688 211714232 212651729 213657683 214778539 215285001 216978708 217098570 218272460 219058704 220404351 221764316 222384321 223727718 224192676 225658832 226355309 227209334 228709781 229105970 230466202 231568816 232033412 233353375 234036983 235177518 236576413 237831373 238500564 239165222 240312162 241490328 242418779 243256273 244931461 245848276 246542610 247615002 248051723 249114254 250278222 251322059 252594463 253511013 254413562 255328627 256706549 257179465 258835658 259723803 260267745 261894545 262931001 263301099 264989879 265048387 266652105 267980184 268421924 269877471 270360508 271529488 272202125 273708140 274635151 275096744 276067239 277803974 278918007 279607045 280904407 281180584 282415071 283011401 284616203 285969845 286289632 287158848 288929561 289904973 290466946 291438091 292116247 293032654 294947379 295085707 296385466 297510823 298202054 299125649 300827443 301565540 302260974 303329669 304520263 305243510 306190586 307482390 308719599 309674115 310947092 311546081 312080560 313583277 314623605 315459812 316773179 317363878 318969835 319453540 320834311 321837172 322308751 323310620 324191598 325036160 326508544 327941865 328709766 329095781 330953508 331736691 332515713 333956214 334606304 335522718 336648264 337278224 338556566 339083249 340067859 341988449 342410143 343538182 344851725 345968184 346693194 347776243 348305702 349493071 350502035 351498231 352055672 353468885 354531495 355042856 356047198 357350464 358181848 359160732 360631058 361198483 362447901 363457621 364343047 365392171 366186188 367722866 368088967 369263696 370020570 371181459 372555918 373140729 374243538 375838092 376381158 377832672 378589588 379296270 380267908 381660935 382966929 383465170 384833188 385013514 386121668 387595782 388886305 389317606 390469299 391764028 392487767 393672650 394977063 395217104 396012157 397596508 398659433 399594713 400818621 401044174 402046526 403802132 404761110 405323171 406965668 407038028 408953204 409328956 410291149 411000398 412363727 413460967 414503067 415576907 416265346 417560809 418340381 419542351 420242349 421561802 422127242 423561889 424346189 425707041 426140284 427080059 428842906 429025249 430422830 431951596 432574241 433217060 434528953 435713482 436361508 437559095 438669132 439329693 440129071 441936677 442788779 443161226 444365052 445408263 446150826 447590077 448793098 449601227 450846634 451395225 452552698 453022084 454682771 455545828 456164331 457465202 458483922 459174318 460641110 461227666 462225813 463427905 464017196 465936489 466407749 467976015 468914415 469834252 470348356 471791512 472976398 473503283 474184232 475859994 476955718 477824255 478303223 479082365 480011253 481018056 482992291 483246270 484584961 485665195 486532103 487528412 488152169 489765587 490083235 491436289 492477226 493871431 494392021 495774003 496995413 497945972 498864729 499327738 500881199 501031035 502153859 503519443 504872586 505818238 506108283 507822806 508174626 509402918 510091320 511812965 512144059 513447800 514043392 515930518 516436729 517740120 518809375 519823585 520051072 521983325 522026150 523832461 524366350 525553559 526827174 527012119 528888085 529160350 530315757 531249700 532118942 533633756 534203457 535209065 536766875 537940637 538171419 539969559 540456203 541226389 542933287 543394828 544536915 545083570 546409657 547640632 548560603 549195811 550935953 551762828 552821608 553181224 554609683 555785385 556645881 557898971 558592960 559993415 560293732 561632959 562615289 563998884 564068913 565867463 566353078 567762351 568369144 569904233 570095106 571610805 572401143 573298469 574534458 575491402 576877622 577609679 578931526 579148604 580771935 581140260 582718615 583793652 584570392 585978764 586979617 587395245 588884964 589199980 590071131 591095258 592120633 593326447 594204342 595509714 596789603 597395284 598163738 599910143 600411993 601848635 602129703 603636230 604612510 605716331 606469227 607234552 608327708 609594663 610076575 611002298 612503292 613766835 614603815 615020721 616524937 617715873 618909002 619472434 620433606 621162015 622348527 623655016 624103181 625472965 626995226 627943366 628054762 629653851 630163941 631171632 632552439 633150313 634120066 635744228 636121850 637826434 638566384 639159213 640874684 641934418 642841404 643041739 644935339 645845863 646489019 647410460 648255410 649576126 650732613 651570447 652808152 653321679 654028597 655150794 656195159 657025242 658167070 659171353 660902846 661648947 662587344 663952602 664757258 665709579 666407243 667827046 668348352 669872001 670876291 671916226 672561678 673794344 674849878 675817286 676800291 677815130 678526026 679652044 680387340 681176572 682412427 683469532 684076433 685661523 686903587 687111255 688397840 689714055 690075514 691972066 692374552 693766645 694438417 695323861 696179849 697016123 698410362 699069221 700106794 701542079 702383963 703042957 704225099 705929345 706640099 707556867 708029405 709140130 710088332 711485017 712725071 713912435 714242834 715627378 716152810 717962562 718921842 719697319 720932015 721736418 722088615 723670394 724775280 725453689 726008737 727373946 728537517 729181903 730946504 731398327 732279984 733193237 734295984 735127336 736207787 737618164 738828317 739329754 740367633 741404696 742418425 743183004 744677554 745677819 746309331 747441448 748404827 749836981 750482715 751989267 752295277 753714947 754652635 755883384 756674813 757340503 758942585 759045217 760766957 761006497 762205675 763353974 764982410 765242459 766622522 767160107 768195045 769827290 770174394 771882788 772013110 773933395 774045961 775938988 776545326 777563116 778513286 779757334 780595675 781277380 782239892 783921202 784844290 785345284 786160848 787036788 788547192 789954279 790236943 791297632 792565506 793264263 794062876 795382650 796331054 797323433 798209969 799698924 800509618 801661707 802352436 803123961 804977796 805070765 806820532 807611041 808037114 809641309 810481764 811393109 812556515 813722183 814199767 815608732 816638501 817461627 818182972 819684742 820327512 821653504 822012061 823461393 824620388 825999130 826151379 827960985 828936791 829515607 830577229 831351813 832521865 833750303 834663873 835737135 836890612 837156348 838296946 839099795 840269582 841345447 842370659 843811579 844251946 845441109 846073946 847472106 848301519 849200514 850235673 851157127 852018838 853275195 854806425 855179211 856412234 857647921 858117001 859538029 860765371 861795260 862177798 863933197 864919779 865958830 866971803 867862176 868677886 869393689 870513723 871847707 872701988 873247074 874668284 875604003 876878377 877338440 878893975 879531187 880643383 881509423 882462942 883461518 884724906 885356657 886478461 887267495 888575468 889949734 890618164 891560142 892563603 893773234 894654036 895988125 896471736 897029455 898635513 899439779 900268313 901333980 902050823 903438224 904881842 905154662 906752360 907235682 908216471 909510134 910527685 911241551 912234838 913605466 914021315 915446771 916781323 917946551 918108160 919043835 920988739 921265935 922424206 923897042 924859094 925702927 926648367 927628428 928067135 929006747 930059667 931579537 932273214 933294045 934939214 935537867 936215472 937334987 938332893 939013458 940893421 941752312 942679195 943592791 944218467 945811485 946563583 947188431 948657073 949760936 950095450 951138401 952553415 953867013 954767822 955579539 956665596 957955948 958795536 959524914 960585393 961139370 962177888 963839360 964084836 965618484 966496905 967732515 968517399 969324392 970099733 971593866 972055203 973692262 974274259 975043041 976464663 977039823 978336908 979374137 980118486 981060059 982094658 983674737 984480687 985842336 986959787 987316009 988359615 989997216 990828717 991890216 992051781 993421332 994132890 995036554 996196164 997966840 998911086 999625776 
90934 95420 93157 95331 95031 94071 97335 90451 95661 96091 95787 90632 94872 93310 94478 99625 98849 93991 98729 92561 95865 98463 95661 90607 97408 91709 90327 95414 91647 94388 93134 91540 99298 96950 91011 90565 94042 96205 91241 90802 96267 98792 91460 93345 93581 98345 96213 95186 92802 92301 94452 96317 95825 93022 97071 99593 93645 96393 90575 96048 97310 94716 90853 93391 99878 94928 92742 99055 94534 96187 98941 94488 90806 95528 93496 96113 93625 99025 90472 94934 95882 90574 93663 94279 94750 90628 95808 90419 90956 94216 99146 90445 98916 99534 98547 96835 96272 95377 94347 96032 99923 95695 91235 91374 92380 98073 99926 91491 92771 90596 96641 91106 95918 93673 90586 96426 96570 94668 95471 90566 90939 93232 90381 95053 96658 93880 99251 98105 97776 90292 99335 98983 94651 99822 93468 93784 94911 95230 94169 92578 92579 98953 99705 93928 99850 99018 92484 98809 99003 99175 94203 98910 93661 97465 97841 95153 93459 98976 94366 90358 90034 95934 92132 91466 99713 96014 92107 92676 90783 99013 91629 91315 90099 92345 90242 92258 97555 98946 99245 92498 90790 92243 98505 94017 98298 99679 91533 96578 93266 95628 93654 90920 98865 94538 94679 93121 98834 94075 96453 96996 91494 98463 92452 90186 98940 96905 98905 91883 90788 92824 98266 94637 96170 95383 94946 96918 98667 96902 97918 92936 99344 92530 91416 92336 94721 99838 99833 91362 92291 91690 90345 91557 93185 95831 97704 96695 90963 91121 99172 91050 91474 91520 98928 98446 98696 92458 98461 97271 95995 92137 98199 93918 92156 95201 90314 98551 98234 94307 92432 94154 98622 98902 91515 99163 94930 94871 97666 99947 91824 98602 90122 94931 93413 91877 98762 92160 94653 92452 94049 99961 91677 92651 97265 92520 97018 92573 95845 94906 99142 94685 91002 98300 90152 90868 97763 91246 97681 90836 91836 96832 92669 92543 93671 90098 97815 92238 90049 92857 96878 96701 96779 98505 98987 98922 91986 99521 99204 93168 96336 97500 97355 98154 96046 98383 94703 97871 99720 98940 94266 94954 94457 92018 91201 92323 94560 95582 90527 96917 94282 95393 96469 91663 92846 94408 95837 95691 90153 91775 90546 96157 90182 98295 97428 98928 90046 96771 99412 95308 98085 90297 90450 92717 97925 94546 93380 91377 90366 97342 97571 97262 96642 97937 95545 91680 98514 95044 90313 96438 97065 96683 96664 97537 99674 91714 91318 99957 91939 90197 91381 90935 91920 98601 91110 98358 92147 90176 96190 93792 97031 92733 94079 97827 97051 91968 90017 96213 90113 93011 92378 93379 91705 92189 95907 91187 98870 96344 98392 92929 91579 92121 92563 93155 93122 90232 96823 92077 95188 91805 97640 93241 95030 97103 98120 91904 99119 96746 94053 91548 92338 95068 96635 90233 92276 95083 93176 91638 90195 93229 94360 95504 93565 93134 92108 99962 93653 96802 94512 98347 95383 94580 96760 94051 95971 91662 96873 92581 95671 90369 90081 97386 97186 94904 93388 99458 98958 94401 94400 94716 98907 94811 96166 92374 97242 98845 98487 91700 96602 99607 91274 97607 99226 96958 93607 90135 94288 92848 90454 90623 91512 91487 99848 93016 90544 93135 96523 99479 90084 98021 90998 95188 95858 93227 91569 94203 97345 92641 95660 99371 96833 98582 91609 91801 90719 93473 99262 96059 91724 98498 90857 91063 92367 93760 95061 95612 90075 90073 92862 95756 94268 94367 96475 91883 91971 97540 96796 90392 93353 96755 96911 96324 93100 91648 99133 94376 94788 99206 95828 93209 98383 98902 94716 90436 98707 95221 99518 94704 94569 92955 96636 96957 93804 97940 91532 97046 96530 96506 94418 99080 99492 96727 98252 98265 91463 92597 93156 94750 98334 99781 96432 93624 99964 95754 98837 94013 97451 93390 96975 94941 95646 90418 91182 96016 97438 95490 96195 99743 96121 90283 97181 99905 95378 93111 96716 91550 93578 93206 99344 91077 94711 94134 95226 91697 99469 93202 91899 98567 94733 97389 93274 98854 92232 93558 92780 91839 93130 95373 91507 96926 92931 98720 97997 96775 98135 98073 98659 96597 96697 93886 99055 91310 99253 94512 94622 96940 98267 92325 92758 91314 95907 96890 96987 95802 91614 93162 96816 97598 90823 96492 99540 93432 94740 94123 96129 94039 91339 93259 90396 92761 95377 97508 90000 98312 93743 93708 93583 93983 97790 98364 99380 94797 92771 96578 90472 91321 99443 91417 91615 92438 96909 95531 95092 93689 99401 90197 93776 90313 97783 97453 90332 90700 95301 98340 90060 94744 96416 97826 96567 92578 95070 90724 95427 96471 96343 95511 97116 95010 90374 90202 90143 94242 91462 95247 95045 90006 93123 94813 97776 98481 96706 98925 96832 94482 99457 95873 97285 99241 97487 93514 91822 94832 99971 96798 90915 90820 94087 92230 98558 94348 91255 95563 91713 92394 92071 98945 91776 97051 92188 93825 99611 94632 93799 97550 97578 90530 96427 90997 98839 94699 93617 90733 95855 90733 95188 92611 91556 91071 95450 96885 92995 97466 92409 98763 96868 97779 97242 93241 98687 94606 92945 91726 95401 93594 92263 95455 95751 97623 97630 94295 92055 94464 90688 95518 91724 99864 91783 91119 96648 91948 96330 90167 96885 99319 96345 92467 92497 90020 97462 98061 90201 93106 90104 99934 94207 97227 90691 99137 98318 92421 92843 93279 96146 91673 98266 96157 97985 92449 92587 94970 91185 91385 91836 97791 94939 99983 94582 90739 90133 94715 99669 91112 91767 97046 93973 99560 91433 97830 90714 97342 93269 93943 96386 99623 90492 95439 93422 92540 94214 91076 97089 96503 92042 97111 93531 97068 92897 90180 92530 91161 94244 91723 90013 96177 92623 94334 92162 91409 98186 97503 96589 92130 99621 96326 93702 94694 99119 98079 96919 92342 96544 93448 99317 92224 96262 97297 94957 93096 95817 92992 90139 98887 91173 99645 93865 97583 97499 92468 90647 90451 99153 98787 92847 97166 94646 91589 97539 96789 90689 91707 95965 99312 93835 99621 91659 92800 92767 91618 93340 91518 95954 91085 95721 92588 99143 93050 98570 90206 94916 96831 92702 91347 97488 91251 90470 92834 99409 91345 91771 93898 91277 94412 96987 92212 94267 94773 96577 91357 95120 94014 90654 94052 90411 90542 93182 99573 92073 93544 99631 90526 99948 95160 92733 97392 95457 97679 94127 96656 95996 92322 94812 98173