1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 2 27 1 28 2 29 1 30 2 31 1 32 2 33 1 34 2 35 1 36 2 37 1 38 2 39 3 40 3 41 3 42 5 43 4 44 5 45 6 46 6 47 6 48 8 49 7 50 8 51 9 52 11 53 10 54 12 55 12 56 14 57 14 58 15 59 15 60 18 61 17 62 18 63 19 64 21 65 23 66 23 67 24 68 26 69 27 70 29 71 29 72 31 73 32 74 33 75 35 76 36 77 37 78 42 79 41 80 46 81 46 82 50 83 51 84 58 85 58 86 63 87 63 88 71 89 71 90 81 91 83 92 89 93 92 94 101 95 104 96 114 97 116 98 129 99 130 100 143 101 145 102 158 103 163 104 181 105 184 106 199 107 203 108 222 109 227 110 248 111 252 112 275 113 279 114 302 115 309 116 333 117 345 118 368 119 379 120 408 121 416 122 444 123 458 124 486 125 502 126 537 127 546 128 581 129 598 130 640 131 651 132 695 133 714 134 755 135 781 136 823 137 844 138 898 139 921 140 978 141 1004 142 1060 143 1098 144 1159 145 1193 146 1258 147 1303 148 1369 149 1415 150 1495 151 1542 152 1621 153 1682 154 1769 155 1827 156 1932 157 1991 158 2097 159 2174 160 2288 161 2365 162 2490 163 2574 164 2706 165 2810 166 2945 167 3050 168 3218 169 3330 170 3493 171 3623 172 3801 173 3937 174 4137 175 4288 176 4495 177 4660 178 4884 179 5057 180 5312 181 5495 182 5774 183 5972 184 6260 185 6480 186 6793 187 7024 188 7361 189 7623 190 7976 191 8247 192 8639 193 8930 194 9342 195 9685 196 10117 197 10454 198 10934 199 11299 200 11811 201 12212 202 12746 203 13179 204 13761 205 14220 206 14831 207 15335 208 16015 209 16530 210 17264 211 17812 212 18575 213 19192 214 20003 215 20658 216 21536 217 22232 218 23158 219 23917 220 24914 221 25742 222 26791 223 27669 224 28813 225 29752 226 30949 227 31953 228 33258 229 34333 230 35717 231 36880 232 38347 233 39597 234 41202 235 42524 236 44208 237 45649 238 47461 239 48984 240 50936 241 52561 242 54617 243 56397 244 58587 245 60494 246 62835 247 64894 248 67379 249 69584 250 72251 251 74596 252 77462 253 79971 254 82997 255 85728 256 88943 257 91828 258 95299 259 98398 260 102120 261 105419 262 109341 263 112904 264 117114 265 120916 266 125392 267 129446 268 134214 269 138552 270 143662 271 148271 272 153687 273 158718 274 164417 275 169750 276 175883 277 181539 278 188058 279 194143 280 201089 281 207515 282 214912 283 221789 284 229630 285 237029 286 245384 287 253173 288 262102 289 270413 290 279870 291 288761 292 298781 293 308235 294 318961 295 328989 296 340303 297 351030 298 363071 299 374503 300 387314 301 399412 302 412961 303 425914 304 440288 305 454028 306 469326 307 483884 308 500135 309 515637 310 532838 311 549290 312 567665 313 585081 314 604480 315 623140 316 643627 317 663343 318 685224 319 706121 320 729285 321 751528 322 776039 323 799598 324 825671 325 850771 326 878245 327 904892 328 934092 329 962295 330 993329 331 1023188 332 1055960 333 1087806 334 1122494 335 1156195 336 1193085 337 1228710 338 1267816 339 1305666 340 1347018 341 1387107 342 1430960 343 1473492 344 1519841 345 1565043 346 1614059 347 1661832 348 1713918 349 1764509 350 1819645 351 1873417 352 1931557 353 1988463 354 2050220 355 2110462 356 2175702 357 2239649 358 2308636 359 2376261 360 2449476 361 2520964 362 2598252 363 2674218 364 2756132 365 2836287 366 2922917 367 3007810 368 3099402 369 3189392 370 3286215 371 3381332 372 3483789 373 3584444 374 3692643 375 3799349 376 3913673 377 4026509 378 4147526 379 4266653 380 4394511 381 4520685 382 4655650 383 4789040 384 4931837 385 5072848 386 5223457 387 5372625 388 5531787 389 5689362 390 5857850 391 6024114 392 6201809 393 6377810 394 6565258 395 6751174 396 6949275 397 7145497 398 7354544 399 7562073 400 7782607 401 8001539 402 8234457 403 8465900 404 8711371 405 8955863 406 9214902 407 9472611 408 9746181 409 10018217 410 10306593 411 10593868 412 10897870 413 11200989 414 11521717 415 11841491 416 12179771 417 12517051 418 12873536 419 13229322 420 13605513 421 13980436 422 14376562 423 14772435 424 15189875 425 15607117 426 16047155 427 16486908 428 16950508 429 17414623 430 17902772 431 18391537 432 18906212 433 19421279 434 19963257 435 20506311 436 21076828 437 21648788 438 22250096 439 22852541 440 23485600 441 24120592 442 24787095 443 25455563 444 26157510 445 26861707 446 27600258 447 28342060 448 29119742 449 29900344 450 30719152 451 31540966 452 32402245 453 33268043 454 34174276 455 35085929 456 36039446 457 36998403 458 38001808 459 39011515 460 40067050 461 41129264 462 42240009 463 43357594 464 44525593 465 45702075 466 46930203 467 48167525 468 49460331 469 50761527 470 52120304 471 53489661 472 54918143 473 56358234 474 57860719 475 59375070 476 60954415 477 62547057 478 64207099 479 65881575 480 67627399 481 69388013 482 71221897 483 73073612 484 75000991 485 76947050 486 78973043 487 81018251 488 83147013 489 85297255 490 87534007 491 89792848 492 92143213 493 94517287 494 96986508 495 99481429 496 102074570 497 104695565 498 107420144 499 110173373 500 113034757 501 115927558 502 118931995 503 121970387 504 125126491 505 128317151 506 131630295 507 134982680 508 138460829 509 141980254 510 145633271 511 149328277 512 153161991 513 157042821 514 161066681 515 165140480 516 169364792 517 173640548 518 178073950 519 182562923 520 187215785 521 191926011 522 196808735 523 201752577 524 206875015 525 212064518 526 217437969 527 222882005 528 228521124 529 234232689 530 240147242 531 246140480 532 252344076 533 258631261 534 265138056 535 271732582 536 278556068 537 285473583 538 292629037 539 299883443 540 307387661 541 314994444 542 322861285 543 330839714 544 339086990 545 347451829 546 356100057 547 364867906 548 373932062 549 383126386 550 392626511 551 402263223 552 412221423 553 422322516 554 432757216 555 443345922 556 454279753 557 465375304 558 476834656 559 488462501 560 500467665 561 512652158 562 525228822 563 537995092 564 551172238 565 564546953 566 578348413 567 592361566 568 606817477 569 621494966 570 636637893 571 652011048 572 667869226 573 683972407 574 700578203 575 717442021 576 734831746 577 752490727 578 770698126 579 789191592 580 808253929 581 827616219 582 847573606 583 867845524 584 888736709 585 909963463 586 931828964 587 954046840 588 976937950 589 1000193175 590 1024149370 591 1048493023 592 1073562658 593 1099040172 594 1125277314 595 1151940220 596 1179392190 597 1207296104 598 1236021647 599 1265217319 600 1295273992 601 1325821684 602 1357264268 603 1389228092 604 1422119741 605 1455558651 606 1489967420 607 1524946673 608 1560936754 609 1597530015 610 1635171626 611 1673446398 612 1712815121 613 1752846180 614 1794016332 615 1835885818 616 1878937185 617 1922719436 618 1967739712 619 2013522793 620 2060593692 621 2108468756 622 2157680150 623 2207736846 624 2259190108 625 2311521865 626 2365306778 627 2420020486 628 2476243149 629 2533437127 630 2592209338 631 2651991644 632 2713416306 633 2775909212 634 2840104580 635 2905418844 636 2972511188 637 3040772431 638 3110880485 639 3182219390 640 3255479586 641 3330024010 642 3406574848 643 3484468476 644 3564448251 645 3645839707 646 3729396024 647 3814429961 648 3901727015 649 3990563585 650 4081756724 651 4174563852 652 4269816625 653 4366763509 654 4466260527 655 4567524734 656 4671440875 657 4777212393 658 4885741809 659 4996207604 660 5109552117 661 5224916249 662 5343273611 663 5463757527 664 5587343149 665 5713152649 666 5842198714 667 5973561730 668 6108295656 669 6245459145 670 6386122649 671 6529323955 672 6676176987 673 6825675756 674 6978971501 675 7135045800 676 7295063100 677 7457976009 678 7625005506 679 7795056562 680 7969385147 681 8146879783 682 8328817822 683 8514064959 684 8703943447 685 8897271449 686 9095414218 687 9297168681 688 9503929020 689 9714462240 690 9930206742 691 10149882561 692 10374981209 693 10604198949 694 10839044148 695 11078191077 696 11323201841 697 11572693727 698 11828286777 699 12088567946 700 12355188294 701 12626696123 702 12904812132 703 13188020569 704 13478097319 705 13773506991 706 14076044295 707 14384146519 708 14699677832 709 15021003098 710 15350054286 711 15685162864 712 16028293724 713 16377747591 714 16735557314 715 17099954305 716 17473028259 717 17852991717 718 18241975153 719 18638136987 720 19043694408 721 19456726252 722 19879519739 723 20310132655 724 20750881698 725 21199781814 726 21659233977 727 22127174664 728 22606094820 729 23093866198 730 23593041997 731 24101451454 732 24621727664 733 25151623334 734 25693849761 735 26246123967 736 26811197919 737 27386742311 738 27975617563 739 28575390112 740 29189018330 741 29814024828 742 30453409289 743 31104653486 744 31770866375 745 32449423011 746 33143529905 747 33850520613 748 34573663469 749 35310226217 750 36063594011 751 36830925973 752 37615721844 753 38415094683 754 39232600612 755 40065280128 756 40916826532 757 41784163704 758 42671106151 759 43574521828 760 44498292995 761 45439212616 762 46401307279 763 47381254788 764 48383191867 765 49403749794 766 50447136236 767 51509914159 768 52596432911 769 53703121418 770 54834483937 771 55986861126 772 57164853851 773 58364736575 774 59591249447 775 60840535293 776 62117479149 777 63418157621 778 64747552532 779 66101650253 780 67485618233 781 68895258720 782 70335922787 783 71803359369 784 73302990984 785 74830478080 786 76391435518 787 77981363765 788 79606060427 789 81260933296 790 82951893699 791 84674252203 792 86434120133 793 88226653024 794 90058119184 795 91923612165 796 93829518824 797 95770815369 798 97754131439 799 99774230876 800 101837962860 801 103939999749 802 106087314628 803 108274483265 804 110508702524 805 112784356572 806 115108857260 807 117476480630 808 119894812825 809 122357995114 810 124873862569 811 127436344204 812 130053525102 813 132719229048 814 135441688954 815 138214614129 816 141046496964 817 143930825149 818 146876369984 819 149876500353 820 152940126249 821 156060502028 822 159246852766 823 162492179649 824 165805981061 825 169181148898 826 172627356323 827 176137347639 828 179721143790 829 183371210042 830 187097876357 831 190893478898 832 194768559603 833 198715285381 834 202744541587 835 206848250511 836 211037597350 837 215304377231 838 219660012815 839 224096109362 840 228624485167 841 233236422858 842 237944115580 843 242738731313 844 247632665323 845 252616930362 846 257704285609 847 262885468605 848 268173643527 849 273559352941 850 279056047230 851 284654066922 852 290367300986 853 296185782710 854 302123795013 855 308171204845 856 314342584452 857 320627611317 858 327041349212 859 333573063207 860 340238310814 861 347026188057 862 353952526883 863 361006258348 864 368203700568 865 375533405819 866 383012177719 867 390628391359 868 398399210847 869 406312742436 870 414386730919 871 422608891102 872 430997444861 873 439539969466 874 448255041359 875 457129987237 876 466183962749 877 475403894722 878 484809527105 879 494387546651 880 504158113879 881 514107643336 882 524256955888 883 534592029427 884 545134291880 885 555869475597 886 566819453935 887 577969722031 888 589342836843 889 600923802297 890 612735843056 891 624763723974 892 637031165726 893 649522660481 894 662262637831 895 675235118049 896 688465239792 897 701936768674 898 715675364628 899 729664505284 900 743930671609 901 758456762464 902 773270060510 903 788353243087 904 803734094063 905 819395011502 906 835364633875 907 851624799098 908 868205020896 909 885086820167 910 902300370416 911 919826759864 912 937697174807 913 955892172368 914 974443740922 915 993332191488 916 1012590172832 917 1032197644606 918 1052188290039 919 1072541421020 920 1093291719547 921 1114418159744 922 1135956179355 923 1157884431004 924 1180239339524 925 1202998947494 926 1226200762261 927 1249822476492 928 1273902439143 929 1298417901833 930 1323408407975 931 1348850519165 932 1374784903252 933 1401187833199 934 1428100815544 935 1455499722374 936 1483427327670 937 1511858718282 938 1540838010161 939 1570339873976 940 1600409378948 941 1631020768454 942 1662220473527 943 1693982016218 944 1726353119655 945 1759306950711 946 1792892225320 947 1827081699998 948 1861925621286 949 1897395884124 950 1933544131778 951 1970341907837 952 2007842041493 953 2046015543098 954 2084916838196 955 2124516142945 956 2164869375594 957 2205946369782 958 2247804326107 959 2290412520395 960 2333829890005 961 2378024822602 962 2423057985979 963 2468897287782 964 2515604747388 965 2563147807517 966 2611590271728 967 2660898668394 968 2711138709513 969 2762276399158 970 2814378938378 971 2867411762217 972 2921444095075 973 2976440474500 974 3032471995663 975 3089502817862 976 3147605517704 977 3206743750060 978 3266992365722 979 3328313868078 980 3390785314135 981 3454368651096 982 3519142715441 983 3585068956909 984 3652228443758 985 3720581601871 986 3790211791154 987 3861078971424 988 3933268445145 989 4006739405119 990 4081579819556 991 4157747764903 992 4235333647860 993 4314295123614 994 4394724598230 995 4476579076182 996 4559953722908 997 4644804420675 998 4731229054309 999 4819182921347 1000 4908766196688