1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 10 0 11 0 12 1 13 0 14 0 15 2 16 0 17 2 18 2 19 0 20 2 21 3 22 0 23 4 24 3 25 3 26 4 27 4 28 4 29 6 30 4 31 8 32 6 33 9 34 9 35 8 36 11 37 13 38 8 39 19 40 14 41 15 42 21 43 18 44 19 45 30 46 19 47 32 48 32 49 29 50 38 51 41 52 36 53 53 54 43 55 56 56 59 57 59 58 67 59 75 60 70 61 93 62 81 63 102 64 105 65 105 66 122 67 133 68 123 69 165 70 145 71 170 72 189 73 183 74 203 75 237 76 211 77 270 78 262 79 281 80 312 81 322 82 335 83 390 84 367 85 437 86 435 87 471 88 509 89 529 90 554 91 632 92 600 93 709 94 713 95 752 96 824 97 858 98 880 99 1016 100 972 101 1108 102 1149 103 1193 104 1290 105 1375 106 1386 107 1579 108 1552 109 1718 110 1797 111 1877 112 1996 113 2138 114 2165 115 2426 116 2416 117 2646 118 2766 119 2886 120 3065 121 3278 122 3313 123 3697 124 3703 125 4000 126 4221 127 4385 128 4619 129 4979 130 5012 131 5532 132 5626 133 5989 134 6318 135 6610 136 6894 137 7426 138 7526 139 8200 140 8391 141 8909 142 9366 143 9803 144 10215 145 10965 146 11130 147 12069 148 12395 149 13075 150 13765 151 14405 152 14945 153 16056 154 16318 155 17550 156 18140 157 19039 158 19996 159 20993 160 21694 161 23238 162 23726 163 25329 164 26252 165 27522 166 28809 167 30265 168 31264 169 33363 170 34151 171 36310 172 37665 173 39411 174 41222 175 43282 176 44653 177 47569 178 48762 179 51607 180 53663 181 56027 182 58476 183 61474 184 63322 185 67255 186 69159 187 72861 188 75800 189 79148 190 82401 191 86595 192 89246 193 94464 194 97294 195 102267 196 106362 197 110966 198 115419 199 121190 200 124867 201 131901 202 136003 203 142556 204 148331 205 154631 206 160584 207 168595 208 173674 209 182968 210 188966 211 197600 212 205516 213 214252 214 222164 215 233044 216 240204 217 252411 218 260913 219 272447 220 283145 221 295071 222 305748 223 320357 224 330283 225 346430 226 358254 227 373546 228 388091 229 404218 230 418468 231 438148 232 451766 233 472932 234 489425 235 509610 236 529083 237 551020 238 569936 239 596099 240 614955 241 642549 242 665109 243 692013 244 717865 245 747318 246 772674 247 807187 248 832910 249 869109 250 899633 251 935200 252 969639 253 1008920 254 1042615 255 1088207 256 1123047 257 1170200 258 1211454 259 1258361 260 1303809 261 1356207 262 1400848 263 1460553 264 1507758 265 1569048 266 1624172 267 1686182 268 1745867 269 1815166 270 1874492 271 1952304 272 2015657 273 2095501 274 2168586 275 2250134 276 2328607 277 2419715 278 2498121 279 2599518 280 2683935 281 2787560 282 2884310 283 2991118 284 3093716 285 3213367 286 3316571 287 3448006 288 3560346 289 3694461 290 3821565 291 3961533 292 4095162 293 4251292 294 4387248 295 4556977 296 4705338 297 4879147 298 5045242 299 5227718 300 5401818 301 5604628 302 5782798 303 6001924 304 6196812 305 6421240 306 6637893 307 6874991 308 7100843 309 7363834 310 7596529 311 7878287 312 8133644 313 8422849 314 8703969 315 9011609 316 9303782 317 9643199 318 9946708 319 10308079 320 10640825 321 11013322 322 11376667 323 11774227 324 12151884 325 12588378 326 12982613 327 13445651 328 13877292 329 14355739 330 14824499 331 15336524 332 15823102 333 16383388 334 16893665 335 17485303 336 18043841 337 18656889 338 19259333 339 19917621 340 20542861 341 21259478 342 21918750 343 22672936 344 23392505 345 24177267 346 24949142 347 25792443 348 26594889 349 27508777 350 28357337 351 29317765 352 30241494 353 31243273 354 32230497 355 33307665 356 34334531 357 35497952 358 36586777 359 37806793 360 38989727 361 40265725 362 41524556 363 42897653 364 44208589 365 45685401 366 47079405 367 48626170 368 50135838 369 51758560 370 53359703 371 55104822 372 56775634 373 58645809 374 60424865 375 62383231 376 64304153 377 66362781 378 68395748 379 70607880 380 72731956 381 75096177 382 77360142 383 79834472 384 82273309 385 84879060 386 87453914 387 90252513 388 92946530 389 95928344 390 98803118 391 101923344 392 105010992 393 108303730 394 111557689 395 115089153 396 118500036 397 122252908 398 125893023 399 129822232 400 133721543 401 137872733 402 141977954 403 146423994 404 150732214 405 155447986 406 160045624 407 164983717 408 169898178 409 175120738 410 180288573 411 185875565 412 191305491 413 197219091 414 203013858 415 209208873 416 215388068 417 221946820 418 228439459 419 235444616 420 242275670 421 249677817 422 256963675 423 264723638 424 272476287 425 280695835 426 288839180 427 297604674 428 306179848 429 315430739 430 324570703 431 334273250 432 343982161 433 354262714 434 364456460 435 375405486 436 386148076 437 397688693 438 409132251 439 421242549 440 433376372 441 446212597 442 458949439 443 472599284 444 486033015 445 500405678 446 514702553 447 529795115 448 544930511 449 560926698 450 576815249 451 593801157 452 610566461 453 628439625 454 646265451 455 665041884 456 683889443 457 703787293 458 723571430 459 744674545 460 765558143 461 787747401 462 809933101 463 833254182 464 856681426 465 881391642 466 905984206 467 932156697 468 958125133 469 985629708 470 1013188898 471 1042110481 472 1071180031 473 1101812366 474 1132333637 475 1164739876 476 1196971948 477 1231015796 478 1265188042 479 1300996616 480 1337010429 481 1374920257 482 1412735797 483 1452799788 484 1492735825 485 1534809020 486 1577110856 487 1621376433 488 1665919529 489 1712762772 490 1759539778 491 1808992810 492 1858393434 493 1910312515 494 1962587898 495 2017227383 496 2072232416 497 2130020362 498 2187794898 499 2248744800 500 2309749377 501 2373729773 502 2438224254 503 2505564664 504 2573388389 505 2644567481 506 2715812316 507 2790825682 508 2866037465 509 2944766641 510 3024214247 511 3107084481 512 3190586464 513 3278131633 514 3365853532 515 3458040659 516 3550625836 517 3647368066 518 3745082733 519 3846919731 520 3949572985 521 4057086502 522 4164939412 523 4278073214 524 4391867025 525 4510584457 526 4630585648 527 4755549229 528 4881569612 529 5013415989 530 5145823571 531 5284478058 532 5424127753 533 5569612867 534 5716773701 535 5869899852 536 6024386726 537 6185851539 538 6348170190 539 6517872243 540 6689006724 541 6867056816 542 7047265131 543 7234648148 544 7423770365 545 7621233813 546 7819946485 547 8027374846 548 8236789337 549 8454414522 550 8674785209 551 8903776320 552 9134992802 553 9376157188 554 9619085329 555 9872307074 556 10128205644 557 10393856374 558 10662981932 559 10942449467 560 11224752325 561 11518910499 562 11815490656 563 12124222006 564 12436502494 565 12760366184 566 13088595608 567 13429229956 568 13773459004 569 14131793714 570 14493401949 571 14869345161 572 15249919109 573 15644266900 574 16044062576 575 16458719867 576 16877931983 577 17313897961 578 17754216286 579 18211454240 580 18674652123 581 19154232384 582 19640590651 583 20144726301 584 20654613808 585 21184387296 586 21719864299 587 22275309296 588 22838359572 589 23420890137 590 24011817876 591 24623999055 592 25243413310 593 25886402887 594 26536799055 595 27210751898 596 27894323882 597 28601075368 598 29318185053 599 30060672095 600 30812242942 601 31591725081 602 32380731494 603 33197543621 604 34026423903 605 34882881630 606 35752093680 607 36651563078 608 37562403706 609 38506273155 610 39462280185 611 40451107109 612 41454995871 613 42491681420 614 43544026803 615 44632421580 616 45735000669 617 46876628247 618 48033628964 619 49229361739 620 50443786540 621 51697221790 622 52969829820 623 54285336551 624 55618503059 625 56997790164 626 58396420244 627 59840778267 628 61308212525 629 62822031438 630 64359291781 631 65947534198 632 67557698995 633 69222316583 634 70911121382 635 72653914851 636 74425095389 637 76251395359 638 78106298341 639 80021742687 640 81964313874 641 83971133584 642 86008061895 643 88108721511 644 90244167919 645 92445103114 646 94680864852 647 96988441521 648 99329516199 649 101746341987 650 104200468615 651 106729849295 652 109301703693 653 111951322610 654 114643298349 655 117420362737 656 120238679583 657 123146286729 658 126099895155 659 129142357482 660 132236547230 661 135423012451 662 138660908508 663 141999545103 664 145388840170 665 148883332309 666 152434359642 667 156090279644 668 159809022165 669 163637214161 670 167527749340 671 171537441076 672 175609211598 673 179804854867 674 184069727822 675 188458438730 676 192923246286 677 197517785632 678 202187813929 679 206998641146 680 211885354129 681 216917899802 682 222034927327 683 227298137480 684 232653344210 685 238162202293 686 243762338753 687 249528732243 688 255387654761 689 261418199756 690 267551556380 691 273857423673 692 280274279826 693 286873017518 694 293581960593 695 300487059451 696 307504755122 697 314724338237 698 322068686522 699 329616601664 700 337298149338 701 345194835635 702 353224438042 703 361485274286 704 369882821305 705 378517815330 706 387303805239 707 396329941512 708 405516729288 709 414957789025 710 424558945091 711 434432518731 712 444471710262 713 454790080993 714 465290789049 715 476074693669 716 487051415865 717 498328473472 718 509798104106 719 521588440764 720 533579039744 721 545897768638 722 558436183423 723 571308485296 724 584411845370 725 597869681773 726 611558904805 727 625625409708 728 639933585321 729 654627346755 730 669585219374 731 684936594595 732 700564502382 733 716610455678 734 732934086861 735 749701311493 736 766759599499 737 784270853664 738 802099048818 739 820390796628 740 839013060483 741 858128017489 742 877575775484 743 897544772588 744 917863721707 745 938714607988 746 959945132720 747 981721540116 748 1003892466297 749 1026643634452 750 1049793236477 751 1073554931407 752 1097736633506 753 1122542869167 754 1147803036847 755 1173705740206 756 1200078848595 757 1227134786872 758 1254667161774 759 1282917966535 760 1311671975548 761 1341158997832 762 1371187959049 763 1401972834383 764 1433317955294 765 1465466111144 766 1498183281014 767 1531743231463 768 1565905130482 769 1600927063639 770 1636595014100 771 1673151869078 772 1710375217269 773 1748542301650 774 1787388228931 775 1827222271870 776 1867775247119 777 1909337005562 778 1951667713486 779 1995043168402 780 2039210739580 781 2084486611509 782 2130571418520 783 2177814212768 784 2225914329881 785 2275197297364 786 2325394353190 787 2376818633790 788 2429183377694 789 2482848867283 790 2537477187936 791 2593461907466 792 2650467555439 793 2708859629049 794 2768336920116 795 2829255061857 796 2891288669725 797 2954847875244 798 3019551868158 799 3085843879709 800 3153349941075 801 3222480509022 802 3292897847786 803 3365005901510 804 3438435801012 805 3513653831475 806 3590231481904 807 3668667531874 808 3748545306429 809 3830325819981 810 3913630384861 811 3998917704019 812 4085769973669 813 4174716837671 814 4265276677958 815 4358010339764 816 4452453955645 817 4549125285914 818 4647599686591 819 4748398070691 820 4851047508216 821 4956149009734 822 5063162082293 823 5172716763678 824 5284296998201 825 5398484444391 826 5514802755608 827 5633843432619 828 5755071710582 829 5879168761735 830 6005528863488 831 6134859356633 832 6266586331839 833 6401363390107 834 6538656215321 835 6679136194381 836 6822199262494 837 6968616735775 838 7117710548794 839 7270274358814 840 7425670315733 841 7584632883422 842 7746562734522 843 7912221808059 844 8080928310733 845 8253554795710 846 8429343260549 847 8609183559781 848 8792367138135 849 8979719597117 850 9170568547489 851 9365778449548 852 9564580674942 853 9767961189047 854 9975073710163 855 10186915529944 856 10402699719607 857 10623354572679 858 10848125868667 859 11077993865345 860 11312093006199 861 11551536445314 862 11795380319043 863 12044741854414 864 12298747489795 865 12558441066735 866 12822976698871 867 13093465586020 868 13368933939712 869 13650637381103 870 13937524530845 871 14230846323759 872 14529633369839 873 14835059797698 874 15146176910871 875 15464243799233 876 15788166239776 877 16119359122780 878 16456652658273 879 16801447114672 880 17152666898734 881 17511633004778 882 17877281765477 883 18251038960010 884 18631676484859 885 19020787429835 886 19417071493597 887 19822095704967 888 20234667031862 889 20656271804870 890 21085717834235 891 21524618912673 892 21971598080326 893 22428447634259 894 22893723822178 895 23369179686667 896 23853492281475 897 24348334370143 898 24852369960189 899 25367424683839 900 25891956604111 901 26427980333223 902 26973894509813 903 27531660027842 904 28099809970173 905 28680227241425 906 29271415418586 907 29875438373552 908 30490571500667 909 31119077724783 910 31759182384969 911 32413078602460 912 33079140256929 913 33759486832245 914 34452443007502 915 35160340725976 916 35881253131726 917 36617720291795 918 37367777466588 919 38133877038029 920 38914216767277 921 39711182796974 922 40522900245173 923 41352002382396 924 42196339065306 925 43058759285858 926 43937089878940 927 44834073094896 928 45747711613873 929 46680692005384 930 47630917362257 931 48601359128971 932 49589620897555 933 50598896257952 934 51626783354967 935 52676348538419 936 53745378805730 937 54836898814438 938 55948564833585 939 57083727950876 940 58239720189728 941 59420119345473 942 60622273170641 943 61849610151889 944 63099678810045 945 64375884587517 946 65675609328174 947 67002629945331 948 68353979785720 949 69733664557279 950 71138757942348 951 72573093602442 952 74033956096883 953 75525179524273 954 77043841409854 955 78594195619441 956 80172947336032 957 81784579218011 958 83425864767565 959 85101090978540 960 86807250799367 961 88548660357821 962 90322060001530 963 92132237949539 964 93975538915115 965 95856976965633 966 97772997473510 967 99728394397723 968 101719838538139 969 103752188369786 970 105821810744898 971 107934092064215 972 110084982057746 973 112280086435161 974 114515491966441 975 116796560165881 976 119119605733802 977 121490097020781 978 123903988159816 979 126367334410041 980 128875653135429 981 131435209194486 982 134041697266018 983 136701114271961 984 139409381985149 985 142172653888406 986 144986428539613 987 147857509199561 988 150780940110664 989 153763720356944 990 156801116652860 991 159899836974341 992 163055369684933 993 166274638193250 994 169552638382321 995 172897009486778 996 176302279222343 997 179776264047341 998 183313763707223 999 186922282598310 1000 190596830848908