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 0 25 0 26 0 27 0 28 2 29 1 30 2 31 1 32 2 33 1 34 2 35 1 36 2 37 1 38 2 39 1 40 2 41 1 42 4 43 2 44 4 45 4 46 5 47 4 48 7 49 5 50 7 51 7 52 8 53 7 54 10 55 8 56 12 57 11 58 12 59 12 60 16 61 13 62 16 63 16 64 18 65 17 66 20 67 18 68 22 69 21 70 24 71 23 72 28 73 25 74 29 75 29 76 32 77 30 78 35 79 33 80 37 81 36 82 39 83 38 84 45 85 41 86 47 87 47 88 53 89 50 90 59 91 56 92 65 93 63 94 71 95 69 96 81 97 76 98 90 99 87 100 99 101 96 102 112 103 107 104 124 105 122 106 137 107 134 108 154 109 148 110 169 111 166 112 189 113 184 114 208 115 203 116 229 117 225 118 250 119 249 120 277 121 271 122 301 123 298 124 328 125 324 126 361 127 353 128 390 129 385 130 421 131 416 132 457 133 452 134 492 135 488 136 529 137 524 138 569 139 562 140 615 141 607 142 656 143 652 144 706 145 698 146 756 147 756 148 811 149 810 150 872 151 868 152 935 153 935 154 1008 155 1006 156 1081 157 1081 158 1160 159 1163 160 1244 161 1256 162 1339 163 1346 164 1438 165 1450 166 1541 167 1556 168 1664 169 1674 170 1782 171 1800 172 1910 173 1932 174 2049 175 2077 176 2199 177 2228 178 2352 179 2387 180 2521 181 2555 182 2704 183 2739 184 2888 185 2931 186 3088 187 3132 188 3298 189 3356 190 3522 191 3582 192 3761 193 3823 194 4009 195 4079 196 4282 197 4353 198 4561 199 4639 200 4857 201 4943 202 5168 203 5270 204 5503 205 5604 206 5850 207 5962 208 6216 209 6336 210 6614 211 6733 212 7017 213 7153 214 7446 215 7588 216 7896 217 8056 218 8372 219 8538 220 8868 221 9047 222 9390 223 9575 224 9947 225 10140 226 10515 227 10723 228 11117 229 11334 230 11743 231 11983 232 12402 233 12650 234 13088 235 13349 236 13804 237 14079 238 14560 239 14843 240 15340 241 15641 242 16156 243 16472 244 17006 245 17349 246 17901 247 18252 248 18829 249 19202 250 19796 251 20188 252 20824 253 21225 254 21876 255 22307 256 22982 257 23435 258 24138 259 24622 260 25348 261 25852 262 26609 263 27142 264 27929 265 28485 266 29320 267 29899 268 30757 269 31372 270 32268 271 32907 272 33838 273 34529 274 35490 275 36205 276 37212 277 37966 278 39010 279 39802 280 40904 281 41727 282 42866 283 43731 284 44923 285 45833 286 47065 287 48033 288 49316 289 50318 290 51655 291 52714 292 54099 293 55206 294 56668 295 57819 296 59331 297 60546 298 62118 299 63387 300 65026 301 66367 302 68066 303 69464 304 71230 305 72697 306 74539 307 76067 308 77999 309 79596 310 81589 311 83265 312 85351 313 87094 314 89256 315 91103 316 93341 317 95259 318 97597 319 99600 320 102027 321 104123 322 106658 323 108839 324 111470 325 113743 326 116480 327 118858 328 121691 329 124190 330 127137 331 129723 332 132783 333 135497 334 138667 335 141486 336 144805 337 147729 338 151162 339 154222 340 157786 341 160966 342 164669 343 167990 344 171826 345 175282 346 179253 347 182853 348 186983 349 190713 350 195013 351 198899 352 203336 353 207375 354 211995 355 216180 356 220963 357 225344 358 230284 359 234816 360 239952 361 244658 362 249974 363 254865 364 260381 365 265451 366 271163 367 276416 368 282336 369 287795 370 293904 371 299585 372 305920 373 311783 374 318338 375 324440 376 331208 377 337519 378 344560 379 351079 380 358342 381 365112 382 372619 383 379625 384 387396 385 394658 386 402680 387 410197 388 418476 389 426264 390 434831 391 442861 392 451736 393 460055 394 469190 395 477792 396 487257 397 496129 398 505891 399 515105 400 525163 401 534667 402 545068 403 554883 404 565613 405 575764 406 586847 407 597323 408 608758 409 619563 410 631374 411 642548 412 654702 413 666262 414 678814 415 690709 416 703657 417 715972 418 729297 419 741994 420 755786 421 768864 422 783061 423 796577 424 811206 425 825146 426 840234 427 854620 428 870173 429 885014 430 901017 431 916340 432 932854 433 948620 434 965665 435 981941 436 999459 437 1016242 438 1034334 439 1051611 440 1070235 441 1088097 442 1107257 443 1125651 444 1145411 445 1164362 446 1184714 447 1204257 448 1225224 449 1245366 450 1266966 451 1287695 452 1309957 453 1331341 454 1354227 455 1376290 456 1399882 457 1422569 458 1446856 459 1470274 460 1495257 461 1519370 462 1545145 463 1569956 464 1596473 465 1622059 466 1649349 467 1675698 468 1703803 469 1730944 470 1759875 471 1787836 472 1817585 473 1846401 474 1877048 475 1906678 476 1938249 477 1968793 478 2001235 479 2032679 480 2066112 481 2098459 482 2132850 483 2166210 484 2201569 485 2235893 486 2272301 487 2307623 488 2345085 489 2381460 490 2419997 491 2457438 492 2497100 493 2535604 494 2576423 495 2616079 496 2658023 497 2698861 498 2742039 499 2784013 500 2828421 501 2871662 502 2917304 503 2961782 504 3008787 505 3054517 506 3102838 507 3149917 508 3199590 509 3248025 510 3299127 511 3348943 512 3401483 513 3452740 514 3506728 515 3559468 516 3615007 517 3669201 518 3726333 519 3782101 520 3840776 521 3898131 522 3958498 523 4017436 524 4079471 525 4140146 526 4203869 527 4266234 528 4331762 529 4395865 530 4463204 531 4529127 532 4598329 533 4666095 534 4737215 535 4806834 536 4879939 537 4951534 538 5026590 539 5100209 540 5177357 541 5252952 542 5332205 543 5409957 544 5491325 545 5571202 546 5654861 547 5736901 548 5822802 549 5907131 550 5995344 551 6081977 552 6172593 553 6261586 554 6354650 555 6446080 556 6541595 557 6635533 558 6733652 559 6830075 560 6930854 561 7029930 562 7133322 563 7235064 564 7341278 565 7445716 566 7554721 567 7662037 568 7773889 569 7884045 570 7998886 571 8111961 572 8229826 573 8345929 574 8466881 575 8586069 576 8710207 577 8832490 578 8959890 579 9085450 580 9216096 581 9344996 582 9479091 583 9611296 584 9748844 585 9884582 586 10025640 587 10164892 588 10309665 589 10452494 590 10600959 591 10747526 592 10899771 593 11050131 594 11206288 595 11360504 596 11520645 597 11678850 598 11842987 599 12005268 600 12173613 601 12339965 602 12512591 603 12683241 604 12860137 605 13035102 606 13216507 607 13395851 608 13581778 609 13765731 610 13956250 611 14144802 612 14340094 613 14533344 614 14733485 615 14931597 616 15136662 617 15339721 618 15549867 619 15757906 620 15973234 621 16186480 622 16407005 623 16625549 624 16851522 625 17075367 626 17306828 627 17536237 628 17773262 629 18008255 630 18251106 631 18491783 632 18740463 633 18987028 634 19241649 635 19494192 636 19754951 637 20013572 638 20280564 639 20545442 640 20818720 641 21089973 642 21369799 643 21647455 644 21933938 645 22218279 646 22511442 647 22802524 648 23102664 649 23400580 650 23707730 651 24012774 652 24327055 653 24639255 654 24960903 655 25280387 656 25609502 657 25936495 658 26273210 659 26607832 660 26952354 661 27294676 662 27647148 663 27997466 664 28357940 665 28716375 666 29085166 667 29451764 668 29828952 669 30204050 670 30589748 671 30973399 672 31367943 673 31760289 674 32163719 675 32565041 676 32977517 677 33387932 678 33809709 679 34229371 680 34660609 681 35089770 682 35530555 683 35969378 684 36420045 685 36868602 686 37329312 687 37787960 688 38258772 689 38727618 690 39208920 691 39688112 692 40179978 693 40669879 694 41172483 695 41673172 696 42186831 697 42698500 698 43223370 699 43746308 700 44282573 701 44816970 702 45364920 703 45910902 704 46470738 705 47028676 706 47600502 707 48170584 708 48754811 709 49337144 710 49933897 711 50528898 712 51138379 713 51746164 714 52368774 715 52989555 716 53625404 717 54259546 718 54908875 719 55556569 720 56219709 721 56881177 722 57558350 723 58233931 724 58925313 725 59615246 726 60321264 727 61025695 728 61746569 729 62465956 730 63201845 731 63936352 732 64687723 733 65437598 734 66204605 735 66970308 736 67753217 737 68534896 738 69334115 739 70132058 740 70947831 741 71762435 742 72595030 743 73426548 744 74276368 745 75125031 746 75992360 747 76858652 748 77743692 749 78627877 750 79531147 751 80433430 752 81355144 753 82276069 754 83216521 755 84156282 756 85116006 757 86074928 758 87054115 759 88032678 760 89031671 761 90030164 762 91049439 763 92068188 764 93108049 765 94147518 766 95208252 767 96268779 768 97350954 769 98432804 770 99536741 771 100640502 772 101766456 773 102892409 774 104041003 775 105189500 776 106360986 777 107532643 778 108727408 779 109922472 780 111141082 781 112359961 782 113602761 783 114845999 784 116113405 785 117381378 786 118673917 787 119966974 788 121285062 789 122603857 790 123947825 791 125292753 792 126663271 793 128034658 794 129432066 795 130830623 796 132255361 797 133681410 798 135134182 799 136588187 800 138069307 801 139551913 802 141061886 803 142573514 804 144112968 805 145654110 806 147223508 807 148794794 808 150394561 809 151996473 810 153627349 811 155260314 812 156922785 813 158587578 814 160282040 815 161979077 816 163706356 817 165436170 818 167196662 819 168960047 820 170754326 821 172551675 822 174380484 823 176212397 824 178076255 825 179943463 826 181842955 827 183746014 828 185681870 829 187621304 830 189594096 831 191570770 832 193581011 833 195595492 834 197644097 835 199696896 836 201784356 837 203876398 838 206003365 839 208135142 840 210302541 841 212474725 842 214683048 843 216896505 844 219146458 845 221401820 846 223694256 847 225992206 848 228327786 849 230669197 850 233048549 851 235434105 852 237858225 853 240288550 854 242758119 855 245234249 856 247749905 857 250272455 858 252835249 859 255404976 860 258015534 861 260633488 862 263292611 863 265959419 864 268668096 865 271384579 866 274143569 867 276910732 868 279720844 869 282539473 870 285401715 871 288272583 872 291187767 873 294111999 874 297080896 875 300059300 876 303083083 877 306116432 878 309195877 879 312285369 880 315421361 881 318567753 882 321761500 883 324965740 884 328218006 885 331481249 886 334792996 887 338116139 888 341488524 889 344872535 890 348306496 891 351752536 892 355248999 893 358758030 894 362318290 895 365891233 896 369516254 897 373154444 898 376845166 899 380549529 900 384307321 901 388078919 902 391904691 903 395744893 904 399639760 905 403549499 906 407514799 907 411495216 908 415531986 909 419584415 910 423693819 911 427819357 912 432002736 913 436202494 914 440460983 915 444736440 916 449071147 917 453423427 918 457835885 919 462266106 920 466757413 921 471267157 922 475838556 923 480428908 924 485081982 925 489754245 926 494490086 927 499245810 928 504065768 929 508906178 930 513811784 931 518738230 932 523730791 933 528744825 934 533825652 935 538928605 936 544099379 937 549292552 938 554554628 939 559839774 940 565194449 941 570572872 942 576021968 943 581495130 944 587039923 945 592609632 946 598251651 947 603919201 948 609660214 949 615427196 950 621268655 951 627136814 952 633080299 953 639051168 954 645098455 955 651173553 956 657326229 957 663507497 958 669767067 959 676056068 960 682424566 961 688822851 962 695301779 963 701811408 964 708402488 965 715024984 966 721730259 967 728467409 968 735288426 969 742142228 970 749080829 971 756053009 972 763111197 973 770203563 974 777383130 975 784597726 976 791900450 977 799239106 978 806667220 979 814131725 980 821687019 981 829279670 982 836963993 983 844686542 984 852502208 985 860356689 986 868305484 987 876294200 988 884378210 989 892502996 990 900724488 991 908987445 992 917348442 993 925751887 994 934254476 995 942800457 996 951447016 997 960137604 998 968930214 999 977767955 1000 986708739