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 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 2 25 1 26 2 27 1 28 2 29 1 30 2 31 1 32 2 33 1 34 2 35 1 36 4 37 2 38 4 39 4 40 5 41 4 42 7 43 5 44 7 45 7 46 8 47 7 48 12 49 9 50 11 51 12 52 14 53 12 54 16 55 14 56 17 57 17 58 18 59 17 60 24 61 20 62 23 63 24 64 27 65 25 66 30 67 27 68 32 69 32 70 33 71 32 72 41 73 36 74 41 75 42 76 48 77 45 78 54 79 50 80 60 81 59 82 65 83 63 84 80 85 72 86 83 87 84 88 97 89 92 90 109 91 105 92 122 93 120 94 134 95 131 96 157 97 149 98 169 99 169 100 191 101 185 102 211 103 207 104 234 105 233 106 255 107 252 108 288 109 278 110 309 111 309 112 343 113 334 114 372 115 366 116 404 117 402 118 436 119 433 120 481 121 470 122 513 123 514 124 561 125 553 126 608 127 602 128 656 129 657 130 708 131 708 132 777 133 771 134 831 135 839 136 907 137 905 138 981 139 985 140 1063 141 1071 142 1146 143 1158 144 1251 145 1256 146 1344 147 1366 148 1459 149 1471 150 1576 151 1594 152 1701 153 1727 154 1834 155 1860 156 1987 157 2009 158 2131 159 2171 160 2303 161 2334 162 2476 163 2515 164 2663 165 2711 166 2859 167 2912 168 3084 169 3130 170 3297 171 3369 172 3546 173 3607 174 3802 175 3874 176 4072 177 4155 178 4358 179 4447 180 4676 181 4762 182 4989 183 5100 184 5339 185 5444 186 5701 187 5819 188 6086 189 6217 190 6486 191 6627 192 6928 193 7065 194 7365 195 7535 196 7850 197 8010 198 8347 199 8526 200 8873 201 9066 202 9422 203 9628 204 10015 205 10219 206 10612 207 10851 208 11261 209 11497 210 11934 211 12188 212 12640 213 12915 214 13378 215 13670 216 14175 217 14468 218 14977 219 15314 220 15849 221 16185 222 16752 223 17118 224 17705 225 18092 226 18698 227 19113 228 19765 229 20187 230 20856 231 21328 232 22024 233 22503 234 23245 235 23758 236 24525 237 25074 238 25868 239 26447 240 27297 241 27894 242 28769 243 29424 244 30340 245 31011 246 31977 247 32693 248 33698 249 34457 250 35497 251 36302 252 37411 253 38238 254 39381 255 40286 256 41478 257 42407 258 43670 259 44654 260 45962 261 47005 262 48365 263 49463 264 50907 265 52046 266 53535 267 54762 268 56317 269 57585 270 59224 271 60562 272 62266 273 63680 274 65443 275 66931 276 68803 277 70340 278 72273 279 73926 280 75939 281 77642 282 79763 283 81558 284 83756 285 85647 286 87930 287 89910 288 92318 289 94369 290 96862 291 99048 292 101640 293 103902 294 106627 295 108992 296 111819 297 114311 298 117239 299 119841 300 122930 301 125622 302 128808 303 131669 304 134984 305 137935 306 141413 307 144502 308 148103 309 151339 310 155072 311 158449 312 162370 313 165861 314 169916 315 173605 316 177807 317 181618 318 186024 319 189995 320 194550 321 198713 322 203428 323 207749 324 212694 325 217166 326 222270 327 226976 328 232269 329 237124 330 242653 331 247704 332 253421 333 258697 334 264608 335 270085 336 276266 337 281920 338 288298 339 294237 340 300836 341 306957 342 313849 343 320202 344 327312 345 333942 346 341294 347 348157 348 355832 349 362922 350 370830 351 378248 352 386430 353 394079 354 402600 355 410529 356 419324 357 427581 358 436659 359 445203 360 454670 361 463485 362 473238 363 482452 364 492529 365 502016 366 512506 367 522335 368 533145 369 543369 370 554536 371 565099 372 576715 373 587618 374 599590 375 610955 376 623319 377 635033 378 647882 379 659995 380 673243 381 685838 382 699506 383 712511 384 726728 385 740143 386 754776 387 768752 388 783866 389 798255 390 813950 391 828833 392 845003 393 860452 394 877138 395 893089 396 910418 397 926867 398 944715 399 961827 400 980241 401 997865 402 1016977 403 1035187 404 1054871 405 1073772 406 1094074 407 1113566 408 1134638 409 1154743 410 1176432 411 1197322 412 1219704 413 1241213 414 1264411 415 1286628 416 1310528 417 1333558 418 1358197 419 1381954 420 1407499 421 1431982 422 1458281 423 1483699 424 1510818 425 1536987 426 1565084 427 1592093 428 1621024 429 1649008 430 1678830 431 1707674 432 1738571 433 1768300 434 1800096 435 1830920 436 1863703 437 1895439 438 1929367 439 1962109 440 1997046 441 2030935 442 2066928 443 2101855 444 2139117 445 2175099 446 2213441 447 2250718 448 2290230 449 2328592 450 2369460 451 2409028 452 2451088 453 2492015 454 2535343 455 2577498 456 2622302 457 2665729 458 2711829 459 2756763 460 2804252 461 2850499 462 2899570 463 2947231 464 2997731 465 3046998 466 3098987 467 3149715 468 3203447 469 3255678 470 3310933 471 3364945 472 3421847 473 3477406 474 3536169 475 3593411 476 3653850 477 3712967 478 3775177 479 3836025 480 3900262 481 3962891 482 4028940 483 4093639 484 4161614 485 4228154 486 4298306 487 4366820 488 4438950 489 4509665 490 4583869 491 4656613 492 4733182 493 4808029 494 4886723 495 4963982 496 5044943 497 5124363 498 5207845 499 5289585 500 5375395 501 5459688 502 5547929 503 5634616 504 5725588 505 5814727 506 5908206 507 6000147 508 6096258 509 6190745 510 6289788 511 6386968 512 6488722 513 6588878 514 6693466 515 6796407 516 6904163 517 7009978 518 7120640 519 7229689 520 7343425 521 7455443 522 7572555 523 7687716 524 7807993 525 7926578 526 8050137 527 8171976 528 8299184 529 8424352 530 8554947 531 8683852 532 8817995 533 8950342 534 9088379 535 9224373 536 9366064 537 9506007 538 9651511 539 9795208 540 9944887 541 10092455 542 10246059 543 10397900 544 10555605 545 10711450 546 10873607 547 11033639 548 11200033 549 11364603 550 11535369 551 11704278 552 11879841 553 12053198 554 12233268 555 12411531 556 12596322 557 12779184 558 12969072 559 13156766 560 13351514 561 13544389 562 13744170 563 13942035 564 14147285 565 14350264 566 14560700 567 14769275 568 14985108 569 15198977 570 15420630 571 15640027 572 15867250 573 16092573 574 16325553 575 16556582 576 16795792 577 17032695 578 17277836 579 17521105 580 17772427 581 18021757 582 18279688 583 18535342 584 18799646 585 19062040 586 19332918 587 19601847 588 19879796 589 20155423 590 20440161 591 20723026 592 21014797 593 21304599 594 21603885 595 21900885 596 22207437 597 22512106 598 22826147 599 23138262 600 23460334 601 23780091 602 24109886 603 24437856 604 24775663 605 25111537 606 25457865 607 25801936 608 26156535 609 26509299 610 26872409 611 27233658 612 27605865 613 27975800 614 28356801 615 28736049 616 29126143 617 29514378 618 29914128 619 30311685 620 30720823 621 31128230 622 31547045 623 31964085 624 32393181 625 32820102 626 33259188 627 33696635 628 34146040 629 34593713 630 35054023 631 35512259 632 35983242 633 36452627 634 36934562 635 37414891 636 37908454 637 38399973 638 38904861 639 39408292 640 39924871 641 40439893 642 40968799 643 41495797 644 42036785 645 42576378 646 43129778 647 43681775 648 44248301 649 44812977 650 45392334 651 45970457 652 46563035 653 47154297 654 47760792 655 48365602 656 48985775 657 49604808 658 50239014 659 50872078 660 51521092 661 52168510 662 52832036 663 53494618 664 54173095 665 54850536 666 55544690 667 56237459 668 56947080 669 57655882 670 58381358 671 59106031 672 59848177 673 60589059 674 61347621 675 62105592 676 62881021 677 63655797 678 64448889 679 65240949 680 66051503 681 66861640 682 67690081 683 68518133 684 69365347 685 70211702 686 71077426 687 71943019 688 72827772 689 73712335 690 74616963 691 75521025 692 76445346 693 77369750 694 78314226 695 79258842 696 80224437 697 81189682 698 82176143 699 83163033 700 84170920 701 85179185 702 86209424 703 87239670 704 88292083 705 89345201 706 90420323 707 91496202 708 92595029 709 93694157 710 94816493 711 95939926 712 97086369 713 98233888 714 99405429 715 100577663 716 101774165 717 102972099 718 104194136 719 105417681 720 106666331 721 107916020 722 109191108 723 110468086 724 111770269 725 113074340 726 114404684 727 115736536 728 117094931 729 118455619 730 119842702 731 121232181 732 122649114 733 124067965 734 125514597 735 126964058 736 128441104 737 129920997 738 131429625 739 132940712 740 134480829 741 136024248 742 137596560 743 139172296 744 140778048 745 142386751 746 144025833 747 145668831 748 147342023 749 149019169 750 150727719 751 152439857 752 154183717 753 155932057 754 157712015 755 159496593 756 161313963 757 163135497 758 164990233 759 166850140 760 168743080 761 170641278 762 172573771 763 174511143 764 176483193 765 178461077 766 180473525 767 182491992 768 184546280 769 186606122 770 188702229 771 190804966 772 192943828 773 195089424 774 197272478 775 199461911 776 201689227 777 203923920 778 206196409 779 208476507 780 210795728 781 213122083 782 215488068 783 217862339 784 220276094 785 222698278 786 225161372 787 227632550 788 230145087 789 232666788 790 235229802 791 237802222 792 240417344 793 243041457 794 245708818 795 248386347 796 251107039 797 253838093 798 256613784 799 259399505 800 262230388 801 265072450 802 267959628 803 270858287 804 273803538 805 276759855 806 279763362 807 282779198 808 285842166 809 288917696 810 292041907 811 295178378 812 298364116 813 301563311 814 304811770 815 308074051 816 311387142 817 314713655 818 318091641 819 321484398 820 324928580 821 328387821 822 331900147 823 335427233 824 339008033 825 342604899 826 346255504 827 349922570 828 353645026 829 357383579 830 361178236 831 364990409 832 368858693 833 372744822 834 376688810 835 380650383 836 384670510 837 388709598 838 392807313 839 396924435 840 401101925 841 405298491 842 409556204 843 413834503 844 418173990 845 422534456 846 426957951 847 431402187 848 435910231 849 440440476 850 445034641 851 449651519 852 454334154 853 459039195 854 463810856 855 468606520 856 473468889 857 478355722 858 483311199 859 488290938 860 493340169 861 498415216 862 503559913 863 508731014 864 513973715 865 519242529 866 524583885 867 529953069 868 535394910 869 540865097 870 546410017 871 551983118 872 557631865 873 563310449 874 569064902 875 574849838 876 580712698 877 586605812 878 592577875 879 598581992 880 604665236 881 610781134 882 616978330 883 623208070 884 629520114 885 635866462 886 642295385 887 648759338 888 655308044 889 661891583 890 668560999 891 675267157 892 682059437 893 688889133 894 695807237 895 702762693 896 709807668 897 716891855 898 724065891 899 731279967 900 738586187 901 745932295 902 753371769 903 760853161 904 768428218 905 776045956 906 783759791 907 791516281 908 799370074 909 807268518 910 815264652 911 823306345 912 831448175 913 839635460 914 847924199 915 856260560 916 864698741 917 873185392 918 881776430 919 890415992 920 899161241 921 907957130 922 916859184 923 925812879 924 934875300 925 943989348 926 953213556 927 962491662 928 971880382 929 981323960 930 990880858 931 1000492713 932 1010219315 933 1020003135 934 1029902254 935 1039859691 936 1049935140 937 1060068970 938 1070322356 939 1080636524 940 1091070797 941 1101566932 942 1112186002 943 1122867118 944 1133672742 945 1144542783 946 1155537967 947 1166598808 948 1177787666 949 1189042286 950 1200426607 951 1211879269 952 1223462239 953 1235114727 954 1246900562 955 1258756172 956 1270746799 957 1282809748 958 1295008463 959 1307280832 960 1319691992 961 1332177027 962 1344802682 963 1357504917 964 1370348493 965 1383269966 966 1396335971 967 1409480213 968 1422770810 969 1436142358 970 1449661109 971 1463262259 972 1477013838 973 1490848130 974 1504834791 975 1518907058 976 1533132540 977 1547445068 978 1561914161 979 1576470761 980 1591185913 981 1605991426 982 1620956447 983 1636013459 984 1651233373 985 1666545665 986 1682022991 987 1697595762 988 1713334512 989 1729170288 990 1745175613 991 1761278527 992 1777553118 993 1793928351 994 1810476344 995 1827126742 996 1843953505 997 1860883172 998 1877991496 999 1895205989 1000 1912600207