812 790
12456 500000000
1000000000
274329 2003092 4080603 5568859 5833713 7748661 7862456 8028157 9089157 9492772 9788280 10121351 10672398 10675750 11009587 12121931 14169151 15460832 17788309 21108650 22805370 24143601 24209196 28090587 28928650 29430415 31129362 31922404 32058302 34146480 34973284 36285821 36607122 37771573 39183484 41802637 42863970 46845432 47074449 47112333 49400499 50170851 51481941 51784563 53523529 54956455 55590980 55996256 56096574 56152195 56668950 56895193 57201370 57941007 57941789 60731381 66458438 66809545 69003364 70219075 71242688 71995150 72216720 72441734 75003067 75492434 76218633 79089392 80677286 82016659 82580528 84653058 84726003 84907683 89255756 90217683 90902940 91353586 91972645 92001376 93285155 93601631 94390877 98084489 98509328 99352097 101677664 103348717 103723108 105930700 106135156 107542729 108152045 109177025 109285489 109724194 110623281 110927183 110979127 112408506 114349524 115289403 115646394 115930775 116427483 118883672 120356700 122427015 122455773 123150143 125396371 125695543 126585444 126836456 127261143 127701143 132406834 133095158 139656501 140156224 141034952 144170848 144887932 145536453 146553564 149133021 151587102 151974737 152396124 152430257 155172047 155858908 156465482 157340351 159206810 159357073 160714811 163765658 164355459 164534948 164780744 165199220 165285031 166173324 166930060 168966924 170447465 170616429 172338957 173490171 173854850 177067083 183268152 183300182 184472043 185541971 185764195 189601949 190771094 191920513 193441093 193724085 195576722 195889389 197323357 198178213 199096886 199530650 200414214 201208102 201953214 203574614 204053193 204914278 204975993 205613637 207911294 209279867 209779756 209901827 211567711 213331420 216943975 217091946 219874000 220463788 222070600 223918902 225198522 226358224 227233311 229569527 230307827 231684707 233545033 234396590 235251009 235808633 235875377 236965928 237579850 237604106 240493691 243101058 243588983 244308967 248059722 250359440 251389917 252274917 252549288 257897534 259749960 269608513 271340063 271530945 272573722 273958275 274048248 275602397 278122429 278681857 280755959 282687087 283745058 289272463 290322630 290562495 291470207 295087729 296460999 297556676 298034849 298667824 300383443 301763669 303361621 303968234 304852752 306091271 307471134 310591139 313468922 314013964 314577104 316219505 317608105 319004647 319076123 321827056 326943880 329924975 330239356 331150299 331562877 333848480 336445738 338098703 338688643 338808035 340268003 341549374 343396751 343936312 345218521 348818008 351808717 352128981 353200430 354852898 355949234 356742408 361151973 362287221 364476043 364560478 366834896 367495725 368445367 372575352 374415000 375103828 376116600 377646510 378556164 382827650 383649959 384007142 384332039 386039020 387347104 387491466 388210142 390572259 390625093 393720513 393813796 395106556 398006333 398305269 400423724 405153433 405638671 405818950 405932257 407904392 410140339 410412140 411068963 411378873 413182765 413461732 414075320 414496493 416681032 417439954 418450793 419996776 420545790 422218636 423338890 424080843 424467597 425411803 425876861 426427361 427491678 429306967 429396878 430000806 432170553 433076657 434398889 437225282 438882148 440977091 442166215 445297744 447360793 447528513 447742841 449270675 449861191 451354200 452800533 454087818 456890788 457409430 457766213 458394993 461593829 462677732 463745000 464017287 464073652 464341391 464370211 467595371 467943007 468687153 471581102 471960690 472171627 474681075 474757966 475077976 476371283 476518483 477797706 478524484 479260379 479425479 481723893 483891811 484279825 484380958 485130658 485820277 491437487 491504524 491699010 492141263 492248863 493797417 493945366 494303264 494917257 495547870 496843560 498844071 499786744 499980377 500881145 501918233 502560580 506980814 507102933 510881318 511854889 513285290 513874855 515694048 515916941 516202426 516266730 516474753 519282957 520863645 521387242 522785893 523051089 525436243 527038652 527481167 529668110 530548041 535801265 536061559 536064362 538017232 540410993 540664486 540876955 541586984 545719324 547787296 550732671 551214970 551405942 551883990 553194165 553200273 553628687 555416818 555531878 555741236 556427328 556685252 556807488 560718771 561521176 561623754 565049002 565486767 566697910 567189129 574111474 574394833 574791745 583584767 583693793 584531570 585394502 588493446 588646960 590038279 596746747 597602669 598094266 601492390 602928389 603308147 603406247 603411712 604515549 606639302 607843984 608709051 609302156 609727183 610536896 610838818 610887881 612913227 613663972 617206078 617418812 617860612 618514713 618540322 619880138 620392270 622035558 622622794 623897237 623953011 624490347 626570832 629034018 629165363 630003886 631943984 632046394 632810356 632923584 633669151 633912204 637022218 637491658 640163709 645237633 645262491 645925002 647288811 647648744 647769967 648159530 650298133 650955185 651087297 651264017 651468605 651880021 652908245 655291583 655672865 656086605 657357999 658350438 658836611 660734702 661557650 665300481 667029485 667383649 669704245 672419755 672584053 679022198 680127127 682366401 683580462 684121012 684123875 686065152 687802443 695454630 696613346 698914066 701383669 701831004 702753544 703098284 704360727 705338426 705447716 709593143 711497519 712339967 714572339 714961024 716874189 717164539 718201110 720340095 720668962 720873809 721639179 722079618 725793127 727449104 727527964 728447645 728679514 729170872 730640052 733287325 735914935 736866903 737035865 737077912 737355499 739787569 739968000 740595639 741959814 744069845 745268619 745329123 745394416 745672569 747671213 750921774 751344671 751353077 753089147 753543574 753765906 753860684 754142236 758026175 758211175 758548848 758755458 758997733 759027142 760237329 760580791 762276391 762312410 763559416 763630009 764808798 766927725 767118524 772220682 772651332 773010863 773108553 773358466 774051588 774856133 775105811 775572559 776848219 777194184 779419920 779426679 779960401 780465873 782077823 783112461 783494756 785763006 787198428 788744655 789176089 791326132 793197097 795273066 796243653 797444112 797837602 798907356 800626062 802236542 802787231 803284389 804004185 805162050 805626860 807178362 813152515 816086568 817282436 818138770 820174280 821858059 822486785 826594960 827143738 827876925 828269092 828685112 830100141 831077424 832602763 834342481 834730948 835105498 836155037 837201752 837616481 837887183 839829367 840858258 841180863 844801807 845043708 846674043 848015563 848518371 850988893 852123133 853569236 853825541 854608550 855455736 855979299 856779678 857643874 861467028 864580037 865441397 868076776 868228305 868914777 870245624 871392107 874153020 874179241 874242295 876053296 876159848 877166124 877444584 878460103 878593026 878907952 878930036 880100505 880418120 880948582 882354600 884152833 884781306 887352880 888084914 889378905 890679594 891534136 892030753 892190497 892897429 892918117 892971972 893416578 893917024 894840313 896706503 897226620 897939620 899442157 902431205 903273772 905477053 905484574 906639111 907132610 908289913 912925158 913203392 915142212 915417007 915845107 916874472 917406246 920622012 922040151 923037014 924156664 925824400 928150976 929646235 930628577 934671800 935133986 935568942 937171895 938616218 938726350 938930163 942331052 942874908 942924191 943216697 943413168 944203336 945186135 945530578 947967291 948021475 948107969 948731535 949232628 950460372 950509354 951570273 953244975 953450268 957097785 958575852 959306309 959577043 959717917 961266266 964043775 964214876 965023437 965378977 965697863 966785017 967548784 967658835 969739122 971140271 972899303 974865400 977196932 977896280 977968417 978499694 979256058 979721846 981079485 983128806 984663406 984803365 985096542 985396180 986527854 986720308 988307748 988709315 990018763 992264926 993666952 998527706 999311637 999419372 999489452 999523502