1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 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 11 49 9 50 11 51 12 52 13 53 12 54 16 55 14 56 16 57 17 58 18 59 17 60 23 61 19 62 22 63 23 64 24 65 24 66 28 67 25 68 28 69 29 70 31 71 29 72 36 73 33 74 37 75 40 76 41 77 42 78 49 79 47 80 53 81 55 82 59 83 60 84 69 85 68 86 74 87 78 88 83 89 85 90 95 91 94 92 102 93 107 94 113 95 116 96 129 97 128 98 138 99 145 100 152 101 157 102 170 103 172 104 185 105 192 106 201 107 207 108 224 109 228 110 241 111 252 112 263 113 271 114 289 115 294 116 311 117 323 118 336 119 347 120 369 121 374 122 393 123 407 124 424 125 436 126 459 127 467 128 491 129 505 130 524 131 537 132 567 133 576 134 603 135 622 136 646 137 661 138 695 139 707 140 742 141 763 142 792 143 814 144 856 145 871 146 911 147 938 148 977 149 1003 150 1051 151 1074 152 1124 153 1156 154 1202 155 1235 156 1297 157 1323 158 1382 159 1424 160 1481 161 1521 162 1589 163 1626 164 1700 165 1747 166 1815 167 1865 168 1950 169 1997 170 2079 171 2139 172 2223 173 2283 174 2380 175 2438 176 2540 177 2610 178 2708 179 2783 180 2900 181 2970 182 3089 183 3173 184 3294 185 3380 186 3513 187 3599 188 3740 189 3840 190 3978 191 4082 192 4243 193 4344 194 4506 195 4629 196 4790 197 4914 198 5094 199 5217 200 5407 201 5546 202 5732 203 5879 204 6090 205 6237 206 6449 207 6617 208 6838 209 7005 210 7244 211 7415 212 7662 213 7854 214 8101 215 8299 216 8575 217 8771 218 9052 219 9274 220 9561 221 9791 222 10094 223 10326 224 10646 225 10897 226 11218 227 11479 228 11829 229 12096 230 12451 231 12745 232 13110 233 13411 234 13805 235 14108 236 14515 237 14846 238 15256 239 15602 240 16046 241 16395 242 16851 243 17231 244 17703 245 18095 246 18594 247 19000 248 19515 249 19950 250 20476 251 20927 252 21495 253 21955 254 22536 255 23037 256 23635 257 24154 258 24787 259 25323 260 25986 261 26552 262 27227 263 27820 264 28543 265 29155 266 29894 267 30549 268 31318 269 31995 270 32808 271 33507 272 34353 273 35102 274 35962 275 36740 276 37659 277 38458 278 39409 279 40258 280 41243 281 42126 282 43157 283 44075 284 45149 285 46120 286 47227 287 48229 288 49404 289 50442 290 51650 291 52756 292 54003 293 55148 294 56465 295 57645 296 59015 297 60264 298 61669 299 62974 300 64452 301 65798 302 67326 303 68747 304 70336 305 71804 306 73466 307 74993 308 76713 309 78326 310 80098 311 81766 312 83643 313 85357 314 87289 315 89106 316 91099 317 92984 318 95069 319 97013 320 99185 321 101222 322 103459 323 105573 324 107921 325 110114 326 112525 327 114828 328 117330 329 119707 330 122328 331 124781 332 127490 333 130074 334 132856 335 135531 336 138454 337 141208 338 144228 339 147110 340 150226 341 153213 342 156458 343 159548 344 162902 345 166131 346 169592 347 172923 348 176549 349 179988 350 183716 351 187325 352 191163 353 194887 354 198895 355 202729 356 206876 357 210878 358 215136 359 219279 360 223720 361 227991 362 232565 363 237018 364 241746 365 246328 366 251243 367 255974 368 261040 369 265981 370 271182 371 276272 372 281706 373 286936 374 292531 375 297984 376 303739 377 309370 378 315336 379 321129 380 327290 381 333308 382 339642 383 345840 384 352425 385 358813 386 365571 387 372218 388 379178 389 386014 390 393247 391 400265 392 407712 393 415016 394 422648 395 430177 396 438102 397 445831 398 453989 399 462006 400 470396 401 478651 402 487332 403 495828 404 504755 405 513564 406 522735 407 531787 408 541311 409 550607 410 560378 411 570036 412 580066 413 590001 414 600391 415 610583 416 621286 417 631838 418 642808 419 653674 420 665033 421 676196 422 687858 423 699410 424 711403 425 723273 426 735674 427 747869 428 760612 429 773249 430 786309 431 799292 432 812827 433 826144 434 840048 435 853828 436 868092 437 882271 438 897003 439 911556 440 926709 441 941753 442 957301 443 972753 444 988828 445 1004698 446 1021193 447 1037610 448 1054538 449 1071398 450 1088895 451 1106188 452 1124168 453 1142053 454 1160479 455 1178865 456 1197900 457 1216759 458 1236309 459 1255789 460 1275857 461 1295863 462 1316570 463 1337109 464 1358372 465 1379589 466 1401394 467 1423177 468 1445712 469 1468046 470 1491167 471 1514243 472 1537954 473 1561662 474 1586119 475 1610426 476 1635561 477 1660641 478 1686410 479 1712170 480 1738755 481 1765194 482 1792459 483 1819738 484 1847718 485 1875714 486 1904572 487 1933280 488 1962901 489 1992531 490 2022882 491 2053302 492 2084611 493 2115800 494 2147936 495 2180085 496 2213038 497 2246053 498 2279995 499 2313861 500 2348697 501 2383594 502 2419321 503 2455123 504 2491948 505 2528668 506 2566426 507 2604286 508 2642990 509 2681834 510 2721710 511 2761524 512 2802455 513 2843465 514 2885399 515 2927500 516 2970682 517 3013848 518 3058140 519 3102582 520 3148008 521 3193589 522 3240336 523 3287078 524 3335025 525 3383158 526 3432280 527 3481643 528 3532228 529 3582810 530 3634679 531 3686748 532 3739900 533 3793321 534 3847982 535 3902722 536 3958804 537 4015113 538 4072573 539 4130314 540 4189415 541 4248607 542 4309176 543 4370062 544 4432137 545 4494552 546 4558393 547 4622326 548 4687775 549 4753540 550 4820558 551 4887994 552 4956893 553 5025966 554 5096595 555 5167588 556 5239949 557 5312726 558 5387069 559 5461636 560 5537816 561 5614446 562 5692472 563 5770987 564 5851182 565 5931588 566 6013731 567 6096371 568 6180477 569 6265158 570 6351549 571 6438243 572 6526786 573 6615814 574 6706449 575 6797683 576 6890744 577 6984176 578 7079477 579 7175398 580 7273005 581 7371236 582 7471432 583 7572009 584 7674611 585 7777890 586 7882877 587 7988637 588 8096428 589 8204658 590 8315038 591 8426102 592 8539059 593 8652820 594 8768677 595 8885108 596 9003747 597 9123175 598 9244597 599 9366840 600 9491388 601 9616511 602 9743954 603 9872310 604 10002708 605 10134061 606 10267808 607 10402169 608 10539059 609 10676861 610 10816847 611 10957903 612 11101410 613 11245684 614 11392551 615 11540419 616 11690665 617 11841963 618 11995910 619 12150696 620 12308174 621 12466810 622 12627863 623 12790114 624 12955187 625 13121084 626 13289898 627 13459915 628 13632496 629 13806413 630 13983191 631 14160968 632 14341812 633 14523887 634 14708741 635 14894967 636 15084255 637 15274659 638 15468175 639 15663131 640 15860980 641 16060280 642 16262856 643 16466558 644 16673625 645 16882221 646 17093793 647 17307025 648 17523638 649 17741501 650 17962927 651 18185907 652 18412137 653 18640086 654 18871556 655 19104469 656 19341037 657 19579339 658 19821051 659 20064543 660 20311853 661 20560627 662 20813262 663 21067812 664 21325857 665 21585903 666 21849894 667 22115467 668 22385180 669 22656826 670 22932218 671 23209761 672 23491393 673 23774812 674 24062491 675 24352276 676 24646072 677 24942042 678 25242387 679 25544637 680 25851344 681 26160371 682 26473502 683 26789034 684 27109192 685 27431301 686 27758181 687 28087469 688 28421119 689 28757365 690 29098342 691 29441533 692 29789708 693 30140407 694 30495766 695 30853796 696 31216882 697 31582340 698 31952930 699 32326324 700 32704565 701 33085655 702 33472098 703 33860980 704 34255360 705 34652688 706 35055059 707 35460559 708 35871589 709 36285288 710 36704758 711 37127295 712 37555244 713 37986445 714 38423449 715 38863383 716 39309273 717 39758504 718 40213393 719 40671706 720 41136212 721 41603733 722 42077552 723 42554957 724 43038235 725 43525237 726 44018659 727 44515327 728 45018683 729 45525716 730 46039010 731 46556236 732 47080178 733 47607653 734 48142030 735 48680393 736 49225364 737 49774418 738 50330587 739 50890487 740 51457649 741 52029083 742 52607346 743 53190035 744 53780187 745 54374264 746 54976011 747 55582223 748 56195679 749 56813838 750 57439726 751 58069899 752 58708075 753 59350987 754 60001551 755 60657003 756 61320672 757 61988856 758 62665385 759 63347021 760 64036619 761 64731448 762 65434887 763 66143074 764 66860112 765 67582485 766 68313227 767 69049566 768 69794853 769 70545267 770 71304908 771 72070192 772 72844347 773 73624324 774 74413735 775 75208611 776 76013106 777 76823653 778 77643431 779 78469417 780 79305343 781 80146961 782 80998746 783 81856905 784 82724760 785 83599226 786 84484005 787 85374924 788 86276508 789 87184753 790 88103255 791 89028684 792 89964984 793 90907816 794 91861703 795 92822761 796 93794550 797 94773630 798 95764164 799 96761526 800 97770585 801 98787193 802 99814981 803 100850596 804 101898137 805 102952952 806 104020036 807 105095012 808 106181854 809 107276883 810 108384383 811 109499683 812 110627739 813 111764217 814 112913109 815 114070592 816 115241278 817 116420102 818 117612328 819 118813505 820 120027598 821 121250880 822 122487903 823 123733551 824 124993341 825 126262427 826 127545161 827 128837587 828 130144352 829 131460347 830 132791028 831 134131592 832 135486537 833 136851558 834 138231716 835 139621587 836 141026831 837 142442591 838 143873269 839 145314708 840 146772006 841 148239463 842 149723144 843 151217810 844 152728191 845 154249952 846 155788158 847 157337281 848 158903317 849 160480914 850 162075067 851 163681085 852 165304463 853 166939337 854 168591809 855 170256636 856 171938702 857 173633313 858 175346139 859 177070974 860 178814394 861 180570749 862 182345121 863 184132851 864 185939503 865 187758937 866 189597799 867 191450202 868 193321653 869 195207023 870 197112232 871 199031024 872 200969988 873 202923370 874 204896610 875 206884496 876 208893286 877 210916208 878 212960354 879 215019698 880 217099734 881 219195344 882 221312661 883 223444964 884 225599559 885 227769954 886 229962175 887 232170729 888 234401970 889 236649136 890 238919410 891 241206472 892 243516398 893 245843366 894 248194222 895 250561740 896 252953478 897 255362963 898 257796172 899 260247502 900 262723758 901 265217495 902 267736697 903 270274399 904 272837067 905 275418796 906 278026417 907 280652667 908 283305404 909 285977617 910 288676051 911 291394325 912 294139877 913 296904952 914 299697633 915 302510979 916 305351562 917 308213118 918 311103195 919 314013688 920 316953233 921 319914339 922 322903947 923 325915735 924 328957131 925 332020162 926 335113484 927 338229399 928 341375310 929 344544312 930 347744332 931 350967187 932 354221523 933 357499781 934 360809250 935 364142993 936 367509295 937 370899364 938 374322477 939 377770691 940 381251449 941 384757851 942 388298057 943 391863371 944 395463268 945 399089319 946 402749554 947 406436608 948 410158984 949 413907863 950 417692609 951 421504990 952 425353088 953 429229206 954 433142368 955 437083195 956 441061577 957 445069019 958 449113566 959 453187722 960 457300445 961 461442204 962 465623278 963 469834647 964 474084934 965 478366244 966 482687684 967 487039800 968 491432785 969 495857611 970 500323121 971 504821001 972 509360957 973 513932985 974 518547630 975 523195813 976 527886270 977 532610802 978 537379197 979 542181152 980 547027754 981 551909307 982 556835067 983 561796612 984 566803758 985 571846260 986 576935203 987 582060792 988 587232661 989 592441793 990 597698614 991 602992509 992 608334746 993 613715528 994 619144393 995 624612399 996 630130205 997 635686684 998 641293724 999 646941042 1000 652638535