1000 1000000000
1221712 2405567 3022079 3209572 3297309 4160482 4699907 5579214 6667811 6983124 7885212 9802989 10028233 10563858 10848770 11160215 13650746 14191833 14666501 14699025 14969711 15253600 15634816 16263508 16905009 17058072 17944293 17969826 19225602 20062603 22163044 28077066 28109702 29428834 32509113 33340304 33365887 33515551 35610107 35965667 36474043 36686158 36972651 37359283 40753090 41513828 44754007 45356420 45443334 46252590 46366488 48613475 49063147 49687215 49889999 49982682 51050801 51373468 51404936 51933767 54437684 54605609 54744183 56058949 56715258 59242635 59891632 60455836 61511638 64537189 64689248 64776272 65979746 67418146 67793705 68873639 69557707 69666040 69816168 70055050 71914684 72362744 72505290 72511886 72786724 73202843 74822143 74944580 75794350 78477262 78657392 78897273 81715810 81851297 82716461 83579644 84207706 84664048 89219250 91367767 92236324 93178658 94523651 94987766 96195470 98894588 100469839 101506073 102727004 103684126 104923969 105626263 106342359 108201408 108308461 108428535 109896069 111022430 111039042 111376442 112129505 113785913 114632766 114982761 115357360 116742413 117462783 117473259 118259170 118330417 119085713 121316723 122403524 124973090 125128285 126051991 126458565 127378504 129505014 129911384 132763460 133099875 133735260 134597936 136972879 137663184 137760644 137910349 139690904 139807965 140741320 141781421 147065224 147107553 148765714 151955568 153238690 153899926 155260638 155697236 157339756 158331627 158764224 158967438 159023649 159197036 160675164 161190477 163247134 163709900 164643507 166577821 166858877 168476973 168715870 169156849 169661178 170152920 170744537 172633357 174553387 174657083 174996744 175220154 175415726 175753062 176744140 178488226 183307989 183349330 184157189 184661928 185328008 185938892 187285926 190408918 190703607 191017891 191712871 193171088 193411475 193576416 193882809 194538432 195541320 197535214 200251964 200750848 203526733 204793964 205641777 206358857 209054835 209509392 210445367 210996308 211235227 212027423 212389179 214000354 217013270 217554555 218233303 219067425 219889180 225825278 228389645 228487250 229452584 233041994 233665588 234166981 235286488 235902140 237352678 237583389 238223265 241427758 242042921 243857256 244193585 245699729 246026674 246861267 246907278 247240296 247287928 247648265 251399105 251951156 253204433 258390311 258459542 258679390 260890738 261228199 261827884 261914057 263548695 264223848 264269700 264861604 265571050 265793717 266421331 267388476 267599470 268886716 269532763 270543281 271458632 271533507 272035741 274540876 275592557 275857396 276830111 276898849 277428842 278362428 278508888 278720725 280109351 281037725 284059291 284395832 284591269 285273470 289405476 289667194 290171499 291495353 291752419 292664215 292898494 293165650 295172512 296359714 298904753 298988293 300332067 300608848 300951844 301657595 301882690 302307135 302483420 302862652 303527816 303841268 304075249 304692688 304769037 306186149 307819976 307855209 311129176 311341777 311648039 311878535 314427569 314727907 315083594 315407981 315964571 318010572 318402250 319682483 320788017 321380541 322213943 322384900 322438185 324058754 324728601 324975806 325530934 327080549 329436397 329677461 330955973 332864309 334791712 335211622 336605141 338128425 338464531 339471242 339723900 340745545 341313121 342712579 342865957 342971815 343399280 345132194 345154182 345164462 346572574 347095301 349980227 352297476 352536997 352598102 353806349 354687279 355202801 355310629 357513426 358594907 358654869 358656008 360517843 360552862 360695754 361673967 361692721 363603179 365032974 366593029 367002055 367497356 368602767 371292556 372447411 373064861 374379469 376419539 376668045 377335753 377922232 378646926 379329410 379696301 380827750 381255815 382111462 382311230 382651892 382907278 388654530 388793831 389563343 391865536 392473658 393042333 394876409 395703151 395999341 396638526 397161446 399040967 399775039 400637151 400954372 401612944 401842982 402042167 402185278 404584123 406126571 407894482 409771082 413517131 413787017 415371519 415546629 416549118 417011219 418441022 420342524 420491680 420798173 421041815 422556942 422678603 422717753 423197031 423221636 423421473 423548845 423747811 425136794 425188802 426947518 427120813 429614701 432468368 433682483 433938822 435115111 437034190 438776600 439417333 439614280 439697033 441467012 441850476 442723348 443616204 444148173 444249795 445758245 446951048 449500565 450201822 450309276 450329734 450662889 450694132 451765061 452755329 453533783 454530978 455700980 455911793 456168656 456537882 458896116 460048846 460393919 461242024 461546217 464119126 465922250 466925569 467342118 468113219 469206294 469539124 470440101 471451173 474971459 477190208 477586535 478646297 481971306 482017799 482556731 483132803 483487684 484323559 484401150 486220142 486331617 488287743 488515477 489626419 490105982 490435745 490903798 490929857 492115290 493271484 493422651 496793210 496864736 496887469 499097662 499684522 500122396 500483722 502538570 502563242 504202600 504796574 506701180 506809624 509188403 511607082 511839477 515402273 517552988 517599461 517687158 517885158 519455804 519602480 523095939 524590463 524744211 524908111 527032013 527372479 527520688 529169488 529267137 529449602 530338656 530338676 531617461 533414108 534841046 535584154 536033239 537406351 537650779 539113575 541027146 541369662 541978508 542024297 543592235 543959190 545541792 545793115 546079229 547987285 549798781 550512722 550646124 551358881 552291161 555026125 555726389 556526346 557009727 557422319 560102059 560582578 561101640 561283531 562993390 566061207 566939646 570650114 570739845 570925220 571677349 572525608 573410812 574449686 574570723 575813592 576260327 577636470 579223114 580387773 580530712 580966461 581841707 582632804 587208405 588442698 588645883 590059440 590966449 591164042 591695632 592050803 593217974 594515912 594550199 594718450 595122292 595301253 597092097 597363273 597920049 599529471 604950331 605432829 606112839 607549857 608022694 608814759 610614820 611440529 613133062 613961945 614104538 614467118 615086681 615780111 616323415 616789911 617489147 617526775 617615849 618586466 619432950 621359216 622726101 623776715 624342976 625011851 626084905 626876009 627463923 628706080 629862839 630277372 632255646 632384874 638222906 639731240 641109312 641754965 641795544 642542474 642980288 643333881 643695224 645671024 647915139 648780007 649443311 649512980 651339197 652320075 653244299 654043566 654639999 654750955 654780631 657213911 658490240 658956287 659118089 661775155 664308763 664456278 664806352 664839938 664893664 665754218 666551509 666924470 669089363 670269873 670277576 671320573 671327901 673077980 673569386 673610325 675314230 675386108 676215022 678096134 679244139 679673925 681025212 681447671 682212586 684104248 684427669 685037570 686534827 688108571 689147123 690237470 691103865 693352621 693704225 694021044 694035619 694368559 694893169 694926185 696998373 698069077 698282699 698381864 698812536 699644734 700727531 701361252 702125546 702483522 703028324 703946860 708267053 708478143 709549585 709564115 711264169 713589903 715787904 715867674 716884906 717567043 717708979 718297514 719267540 721697122 722110926 722293712 722915009 724080689 725180655 725912648 726725132 726820725 727972607 728278459 729593990 731810667 732859754 734000375 735468517 737404912 739467985 739577677 741059888 741269030 742187929 743126959 743219856 743580937 744441487 745040667 745146680 745936563 746106951 748976351 749621062 752016549 753510040 754354690 757139343 758427253 758985900 759101575 759707570 759808084 762923580 763093317 766004215 772084468 772488339 772616393 773298214 773627036 774434654 777445900 779159701 785073696 787786549 789003768 790081000 790604124 790637223 791509906 792074513 792256742 794644039 795251773 795365953 796215007 798055943 798455660 798919480 799255963 799433953 799600661 799693587 800346999 800521565 801026656 801220406 803858253 806104604 808496411 808840461 809046206 809193446 810098467 810452582 810827963 811852776 812136764 813610512 813834462 816544327 817364870 817595505 818406190 819809576 821965848 822739135 823203561 827858004 829065592 829804657 830480332 832399952 833436968 833719679 834183820 834658430 835453364 836296124 837036991 838064372 838259881 842450041 843922680 846168040 846281636 846892774 848485724 851562978 854488453 854563561 855759265 855886130 855991580 856686502 857144641 857648994 857772345 858816847 859048437 859850876 861858850 862454230 863053338 864679672 865340202 866734313 867691097 874024106 874463838 875544286 878063854 878222539 878411053 878875242 879664987 880309396 881250215 882271596 883584222 885702230 888918906 889077230 889538686 890143523 890476278 893027936 893039215 893092518 893158981 893452603 893592464 893856235 894746981 897105842 897606608 898007344 900732290 902227512 903854201 905605199 908185260 908338947 908860472 909328449 912959739 914586461 915340721 915959134 918756599 918879652 919024732 921771556 922375531 923922708 924667754 924922605 925021949 925185054 925969494 925978545 926251647 927732262 928219550 928283929 929976413 930312246 930846642 931905952 933685403 934139028 935126331 936266917 938969779 940530157 941224356 941924760 943850712 944989293 947299119 947836301 949472459 950793462 951356465 951656166 951793737 952462654 955593363 958667346 960403015 963339224 965075285 966619702 966837914 967896375 970899177 972041343 972162949 972923706 973046258 974527949 974645347 975391048 975457109 975876985 976028491 979637230 979905916 980017374 981978905 982340109 982871825 985242504 985444788 986533357 987331952 987379285 987544013 987812051 988512475 992003962 993121174 994014325 997068019 998879382 999070915