0 1 1 0 2 0 3 1 4 0 5 0 6 1 7 1 8 0 9 1 10 1 11 0 12 1 13 1 14 1 15 2 16 1 17 1 18 2 19 1 20 1 21 4 22 2 23 1 24 4 25 2 26 1 27 4 28 4 29 2 30 5 31 4 32 2 33 6 34 4 35 5 36 8 37 5 38 5 39 9 40 6 41 5 42 13 43 8 44 6 45 14 46 9 47 7 48 15 49 14 50 10 51 18 52 15 53 11 54 21 55 16 56 17 57 26 58 19 59 18 60 29 61 22 62 19 63 37 64 28 65 23 66 41 67 31 68 27 69 45 70 41 71 34 72 53 73 45 74 38 75 61 76 49 77 50 78 72 79 58 80 55 81 80 82 67 83 60 84 98 85 80 86 71 87 109 88 89 89 82 90 121 91 110 92 98 93 139 94 122 95 109 96 157 97 135 98 134 99 182 100 156 101 149 102 202 103 177 104 165 105 240 106 206 107 191 108 267 109 229 110 217 111 295 112 272 113 252 114 335 115 303 116 280 117 376 118 335 119 332 120 429 121 382 122 370 123 476 124 430 125 410 126 552 127 491 128 467 129 612 130 545 131 525 132 675 133 632 134 599 135 759 136 702 137 665 138 847 139 776 140 770 141 956 142 874 143 856 144 1058 145 976 146 946 147 1205 148 1102 149 1065 150 1332 151 1220 152 1189 153 1466 154 1391 155 1341 156 1637 157 1540 158 1485 159 1818 160 1697 161 1690 162 2033 163 1896 164 1871 165 2242 166 2106 167 2062 168 2522 169 2356 170 2302 171 2779 172 2600 173 2556 174 3053 175 2927 176 2857 177 3388 178 3228 179 3153 180 3744 181 3548 182 3544 183 4157 184 3938 185 3908 186 4568 187 4353 188 4295 189 5092 190 4835 191 4764 192 5594 193 5317 194 5264 195 6131 196 5928 197 5842 198 6768 199 6515 200 6423 201 7446 202 7142 203 7152 204 8218 205 7885 206 7858 207 9003 208 8678 209 8613 210 9967 211 9580 212 9503 213 10917 214 10500 215 10454 216 11934 217 11622 218 11532 219 13112 220 12732 221 12635 222 14369 223 13921 224 13970 225 15784 226 15297 227 15299 228 17243 229 16768 230 16724 231 18981 232 18420 233 18366 234 20729 235 20126 236 20122 237 22600 238 22148 239 22088 240 24732 241 24190 242 24125 243 27012 244 26379 245 26526 246 29552 247 28869 248 28961 249 32198 250 31533 251 31572 252 35276 253 34494 254 34531 255 38417 256 37583 257 37698 258 41780 259 41165 260 41212 261 45563 262 44833 263 44885 264 49614 265 48764 266 49125 267 54091 268 53176 269 53480 270 58783 271 57900 272 58148 273 64142 274 63113 275 63373 276 69671 277 68585 278 68969 279 75593 280 74821 281 75134 282 82189 283 81270 284 81616 285 89254 286 88179 287 88975 288 97005 289 95858 290 96603 291 105165 292 104083 293 104775 294 114357 295 113100 296 113838 297 123917 298 122606 299 123547 300 134158 301 133292 302 134177 303 145467 304 144423 305 145395 306 157574 307 156345 308 157966 309 170784 310 169490 311 171084 312 184734 313 183566 314 185134 315 200280 316 198916 317 200599 318 216544 319 215142 320 217160 321 233956 322 233187 323 235197 324 253052 325 252086 326 254277 327 273481 328 272317 329 275444 330 295670 331 294481 332 297642 333 319157 334 318199 335 321405 336 345105 337 343944 338 347398 339 372362 340 371210 341 375210 342 401518 343 401278 344 405369 345 433311 346 432891 347 437325 348 467299 349 466709 350 472496 351 504082 352 503554 353 509511 354 543074 355 542947 356 549102 357 585844 358 585549 359 592182 360 630898 361 630723 362 638233 363 679044 364 680202 365 687992 366 731303 367 732364 368 740774 369 787130 370 788111 371 798492 372 847356 373 848571 374 859382 375 911253 376 913153 377 924444 378 980925 379 982777 380 994929 381 1054457 382 1056662 383 1070205 384 1132966 385 1137134 386 1151299 387 1217853 388 1222118 389 1237375 390 1308462 391 1312851 392 1330995 393 1405940 394 1410878 395 1429912 396 1509394 397 1515494 398 1535496 399 1621644 400 1627979 401 1649462 402 1740270 403 1747385 404 1771065 405 1866811 406 1876822 407 1901729 408 2003185 409 2013672 410 2040449 411 2148616 412 2159631 413 2190644 414 2304685 415 2316819 416 2349490 417 2470331 418 2484419 419 2518871 420 2649329 421 2664198 422 2701137 423 2838656 424 2855040 425 2895436 426 3040428 427 3061091 428 3103732 429 3257257 430 3279090 431 3324849 432 3488259 433 3511374 434 3563346 435 3735623 436 3760838 437 3815724 438 3998128 439 4026574 440 4084578 441 4280818 442 4311020 443 4373116 444 4579966 445 4612898 446 4680403 447 4898468 448 4937737 449 5009148 450 5239881 451 5281540 452 5358026 453 5603254 454 5647519 455 5733117 456 5991620 457 6039621 458 6130150 459 6403646 460 6456889 461 6552693 462 6846048 463 6902686 464 7005114 465 7314288 466 7375634 467 7486454 468 7812333 469 7883100 470 8000455 471 8345027 472 8420252 473 8545715 474 8911448 475 8991502 476 9130335 477 9515802 478 9602215 479 9749181 480 10156714 481 10251490 482 10407149 483 10843111 484 10943986 485 11110178 486 11569560 487 11678321 488 11857411 489 12341508 490 12464304 491 12654033 492 13165564 493 13296192 494 13498694 495 14040988 496 14180036 497 14402172 498 14973597 499 15123142 500 15358402 501 15962123 502 16124845 503 16374099 504 17018425 505 17191600 506 17457351 507 18136132 508 18322214 509 18607624 510 19322744 511 19529726 512 19832106 513 20587274 514 20807446 515 21129714 516 21929413 517 22163688 518 22514771 519 23357204 520 23608406 521 23980270 522 24869730 523 25141480 524 25535442 525 26482760 526 26771857 527 27191316 528 28189027 529 28498821 530 28948034 531 29998859 532 30339698 533 30815552 534 31924547 535 32286915 536 32793399 537 33966598 538 34351911 539 34900610 540 36136128 541 36548274 542 37129337 543 38433006 544 38876891 545 39492294 546 40878216 547 41350139 548 42004533 549 43463752 550 43968266 551 44667406 552 46203831 553 46754308 554 47494688 555 49115196 556 49700019 557 50487076 558 52199789 559 52821164 560 53669891 561 55472998 562 56136280 563 57034724 564 58936147 565 59647970 566 60599099 567 62617177 568 63373356 569 64383556 570 66507687 571 67314398 572 68391461 573 70627228 574 71501768 575 72641867 576 74998625 577 75926992 578 77137516 579 79626206 580 80611787 581 81912134 582 84531280 583 85581443 584 86957295 585 89717654 586 90841338 587 92297136 588 95222540 589 96415156 590 97959676 591 101037765 592 102307746 593 103951510 594 107190233 595 108559988 596 110299002 597 113711080 598 115163951 599 117008279 600 120608451 601 122149538 602 124124306 603 127911855 604 129551242 605 131639556 606 135629072 607 137378815 608 139587252 609 143809694 610 145665041 611 148005617 612 152446861 613 154419380 614 156906297 615 161577613 616 163696365 617 166325784 618 171244470 619 173489884 620 176275554 621 181461464 622 183841083 623 186815599 624 192269411 625 194797039 626 197940772 627 203682276 628 206374225 629 209696793 630 215766207 631 218618002 632 222135835 633 228517421 634 231544978 635 235277257 636 241986934 637 245227932 638 249171546 639 256232818 640 259664582 641 263838374 642 271277976 643 274911552 644 279357832 645 287178806 646 291033121 647 295729483 648 303958665 649 308055886 650 313016247 651 321705901 652 326042558 653 331289378 654 340422563 655 345020502 656 350579769 657 360178872 658 365086934 659 370957191 660 381054122 661 386246525 662 392453592 663 403084348 664 408577188 665 415175988 666 426347399 667 432166718 668 439132233 669 450880698 670 457056657 671 464408904 672 476802381 673 483333570 674 491103321 675 504124437 676 511040795 677 519263324 678 532943434 679 540308320 680 548985189 681 563367576 682 571152450 683 580318993 684 595452130 685 603680348 686 613407884 687 629304482 688 638011870 689 648273348 690 664982750 691 674210331 692 685034431 693 702645048 694 712395078 695 723823979 696 742319341 697 752632813 698 764714420 699 784138275 700 795097539 701 807838432 702 828249461 703 839824081 704 853272542 705 874736022 706 886959666 707 901208429 708 923745928 709 936667824 710 951688990 711 975367363 712 989043235 713 1004877718 714 1029812063 715 1044250226 716 1060955819 717 1087132711 718 1102389358 719 1120031056 720 1147511329 721 1163693738 722 1182286050 723 1211149206 724 1228226618 725 1247835502 726 1278169433 727 1296190000 728 1316936261 729 1348775624 730 1367806813 731 1389663788 732 1423099080 733 1443216578 734 1466242306 735 1501423475 736 1522645285 737 1546918794 738 1583838791 739 1606241985 740 1631851394 741 1670594536 742 1694319122 743 1721291142 744 1761965066 745 1786982500 746 1815407252 747 1858130252 748 1884508872 749 1914544036 750 1959369764 751 1987201944 752 2018825366 753 2065876223 754 2095264824 755 2128558317 756 2178029835 757 2209007810 758 2244079275 759 2295975771 760 2328648779 761 2365617658 762 2420055628 763 2454606604 764 2493517984 765 2550642994 766 2587049604 767 2628026598 768 2687997762 769 2726356438 770 2769605135 771 2832503359 772 2872940498 773 2918448242 774 2984438932 775 3027094402 776 3074975881 777 3144314256 778 3189243445 779 3239645812 780 3312354861 781 3359702346 782 3412787537 783 3489027687 784 3539032734 785 3594872962 786 3674840848 787 3727493492 788 3786256730 789 3870166238 790 3925601941 791 3987557828 792 4075528550 793 4133920202 794 4199073020 795 4291328273 796 4352865976 797 4421375782 798 4518249002 799 4583020987 800 4655088332 801 4756631660 802 4824835373 803 4900679741 804 5007113407 805 5079062182 806 5158795083 807 5270384379 808 5346089921 809 5429940134 810 5546972366 811 5626624201 812 5714944855 813 5837594074 814 5921428352 815 6014251661 816 6142819029 817 6231093810 818 6328642314 819 6463563807 820 6556414664 821 6658961383 822 6800333170 823 6898029281 824 7005871444 825 7153994918 826 7256947265 827 7370252493 828 7525485152 829 7633740733 830 7752820036 831 7915547512 832 8029370314 833 8154686720 834 8325159087 835 8444871031 836 8576500609 837 8755123504 838 8881074348 839 9019325368 840 9206669239 841 9339062052 842 9484305604 843 9680531515 844 9819732821 845 9972370830 846 10177890066 847 10324439744 848 10484719108 849 10700012814 850 10854012593 851 11022355468 852 11247940772 853 11409756617 854 11586770903 855 11823003257 856 11993073009 857 12178901279 858 12426326271 859 12605123348 860 12800190926 861 13059555416 862 13247378379 863 13452188618 864 13723747627 865 13921094830 866 14136190448 867 14420503661 868 14628085095 869 14853824174 870 15151538266 871 15369537700 872 15606492433 873 15918300118 874 16147222575 875 16396191910 876 16722593762 877 16963033605 878 17224258264 879 17565987076 880 17818584350 881 18092648781 882 18450682934 883 18715870122 884 19003455741 885 19378184288 886 19656637802 887 19958476449 888 20350658949 889 20643313118 890 20959917723 891 21370422030 892 21677580753 893 22009725652 894 22439478572 895 22761835967 896 23110571918 897 23560272840 898 23898634304 899 24264344028 900 24734975730 901 25090205532 902 25473689085 903 25966533813 904 26339250703 905 26741428819 906 27257064561 907 27648184609 908 28070042917 909 28609497695 910 29020250972 911 29462516602 912 30026953291 913 30457816708 914 30921535549 915 31512192585 916 31964116774 917 32450671294 918 33068519081 919 33542593508 920 34052568787 921 34698923407 922 35196313278 923 35730800780 924 36407343243 925 36928924272 926 37489165949 927 38196737847 928 38743747892 929 39331069262 930 40071058277 931 40645117372 932 41260539830 933 42034501657 934 42636332703 935 43281265959 936 44090853282 937 44721753873 938 45398017224 939 46244568278 940 46906009112 941 47614472799 942 48499747228 943 49193296329 944 49935444691 945 50861646582 946 51588531994 947 52366037134 948 53334372740 949 54096263534 950 54910905095 951 55923242767 952 56722273294 953 57575474510 954 58633892135 955 59471131093 956 60364788036 957 61471488112 958 62348700697 959 63285207923 960 64442025747 961 65361192903 962 66341818625 963 67551103055 964 68514330729 965 69541087380 966 70805728338 967 71814725197 968 72889859487 969 74211563992 970 75268576019 971 76394472879 972 77775750223 973 78883589842 974 80062218505 975 81505839498 976 82666056590 977 83899962172 978 85408857826 979 86623845550 980 87916179935 981 89492854630 982 90765275078 983 92117857132 984 93765440941 985 95098117156 986 96513666897 987 98235948492 988 99631241980 989 101112771706 990 102912141437 991 104373068360 992 105923768203 993 107803588044 994 109333853949 995 110956431935 996 112920390521 997 114522208927 998 116220074681 999 118272066656 1000 119948671394