0 1 1 1 2 2 3 2 4 3 5 3 6 4 7 4 8 6 9 5 10 7 11 8 12 8 13 9 14 13 15 10 16 13 17 15 18 16 19 18 20 21 21 17 22 24 23 28 24 26 25 26 26 36 27 32 28 38 29 42 30 40 31 46 32 52 33 48 34 63 35 63 36 59 37 63 38 85 39 77 40 81 41 92 42 89 43 102 44 116 45 98 46 122 47 134 48 130 49 140 50 157 51 145 52 165 53 182 54 190 55 191 56 207 57 195 58 235 59 259 60 232 61 252 62 293 63 279 64 311 65 316 66 323 67 342 68 381 69 370 70 404 71 431 72 412 73 447 74 504 75 477 76 524 77 540 78 560 79 596 80 621 81 599 82 682 83 731 84 702 85 719 86 809 87 796 88 849 89 909 90 900 91 935 92 1004 93 982 94 1101 95 1121 96 1114 97 1187 98 1283 99 1261 100 1313 101 1380 102 1409 103 1504 104 1583 105 1516 106 1668 107 1716 108 1746 109 1821 110 1937 111 1936 112 2014 113 2121 114 2154 115 2226 116 2335 117 2324 118 2541 119 2629 120 2576 121 2682 122 2870 123 2857 124 3063 125 3125 126 3175 127 3292 128 3450 129 3481 130 3641 131 3793 132 3811 133 3958 134 4234 135 4146 136 4361 137 4507 138 4628 139 4828 140 4929 141 4954 142 5295 143 5455 144 5486 145 5655 146 5941 147 5962 148 6264 149 6431 150 6537 151 6767 152 7033 153 7096 154 7467 155 7610 156 7677 157 7957 158 8383 159 8458 160 8736 161 8943 162 9148 163 9471 164 9804 165 9786 166 10342 167 10615 168 10726 169 11115 170 11485 171 11589 172 12041 173 12371 174 12697 175 12971 176 13373 177 13501 178 14191 179 14545 180 14650 181 15134 182 15694 183 15823 184 16409 185 16787 186 17184 187 17652 188 18198 189 18385 190 19110 191 19526 192 19839 193 20464 194 21156 195 21294 196 22078 197 22597 198 23083 199 23729 200 24263 201 24616 202 25658 203 26114 204 26525 205 27166 206 28134 207 28499 208 29480 209 30101 210 30526 211 31373 212 32232 213 32719 214 33930 215 34504 216 35106 217 35986 218 37148 219 37629 220 38659 221 39389 222 40414 223 41471 224 42347 225 42832 226 44329 227 45251 228 45988 229 47310 230 48523 231 49029 232 50572 233 51550 234 52648 235 53753 236 55129 237 55897 238 57803 239 58838 240 59696 241 61271 242 62747 243 63734 244 65592 245 66605 246 68089 247 69534 248 71142 249 72338 250 74395 251 75778 252 77058 253 78838 254 80935 255 81865 256 84005 257 85644 258 87496 259 89417 260 91123 261 92496 262 95467 263 96864 264 98657 265 100843 266 103065 267 104636 268 107370 269 109332 270 111282 271 113873 272 116203 273 117914 274 121264 275 122841 276 125244 277 128139 278 131026 279 132967 280 135941 281 138216 282 141174 283 144028 284 146927 285 149136 286 153081 287 155541 288 158281 289 161534 290 164925 291 167368 292 171533 293 174439 294 177635 295 181068 296 184466 297 187632 298 192451 299 195171 300 198501 301 202595 302 207099 303 209939 304 214642 305 217992 306 222368 307 226844 308 230882 309 234434 310 239930 311 243647 312 248078 313 253158 314 257947 315 261374 316 267463 317 271590 318 276958 319 282127 320 286879 321 291725 322 298392 323 302627 324 307983 325 313683 326 319738 327 324679 328 331794 329 336757 330 342628 331 349023 332 355328 333 360778 334 369014 335 373890 336 380420 337 387892 338 394688 339 400761 340 408915 341 415033 342 423086 343 430146 344 437336 345 444153 346 453799 347 460163 348 468211 349 476843 350 485125 351 492251 352 502246 353 509616 354 518744 355 527629 356 536187 357 544777 358 556393 359 563696 360 573051 361 583492 362 593725 363 602364 364 613965 365 622565 366 634051 367 644872 368 655136 369 665129 370 678023 371 687424 372 699389 373 711545 374 723229 375 733488 376 747930 377 758580 378 771525 379 784042 380 796265 381 808949 382 824871 383 835412 384 849446 385 863546 386 877419 387 890883 388 907414 389 919755 390 935144 391 950356 392 965351 393 979796 394 998360 395 1010926 396 1027860 397 1045450 398 1061973 399 1076621 400 1095849 401 1111104 402 1130351 403 1148146 404 1165000 405 1182552 406 1204065 407 1220077 408 1239784 409 1259876 410 1279183 411 1297443 412 1320650 413 1337849 414 1360494 415 1380942 416 1401462 417 1423444 418 1448280 419 1466114 420 1489542 421 1513427 422 1536786 423 1558392 424 1585091 425 1605523 426 1632186 427 1657241 428 1680536 429 1705596 430 1735309 431 1757288 432 1785218 433 1812812 434 1838931 435 1864563 436 1896722 437 1921959 438 1952171 439 1980956 440 2009422 441 2038779 442 2073504 443 2098201 444 2131267 445 2163689 446 2195601 447 2227000 448 2262625 449 2291305 450 2327044 451 2361476 452 2395570 453 2430014 454 2469156 455 2498375 456 2538006 457 2576817 458 2612682 459 2648735 460 2690917 461 2724883 462 2768368 463 2807491 464 2845316 465 2886468 466 2932505 467 2969119 468 3014214 469 3057637 470 3100324 471 3141998 472 3192590 473 3232056 474 3281492 475 3327487 476 3372310 477 3420743 478 3474739 479 3515710 480 3567427 481 3619994 482 3670416 483 3718820 484 3775519 485 3822739 486 3880388 487 3934256 488 3986585 489 4042188 490 4103765 491 4152368 492 4215690 493 4274844 494 4330309 495 4388720 496 4455926 497 4510496 498 4577272 499 4637875 500 4699265 501 4765946 502 4837745 503 4892652 504 4964219 505 5033114 506 5100233 507 5169095 508 5244088 509 5307078 510 5384266 511 5457233 512 5529196 513 5602993 514 5684501 515 5750858 516 5834748 517 5915696 518 5991546 519 6068639 520 6156729 521 6231391 522 6322080 523 6404301 524 6485671 525 6571860 526 6668453 527 6746116 528 6840830 529 6932238 530 7019951 531 7112569 532 7215438 533 7298782 534 7401579 535 7497925 536 7592212 537 7696148 538 7803797 539 7890235 540 8001866 541 8107301 542 8212291 543 8316889 544 8430657 545 8529874 546 8649255 547 8761083 548 8870374 549 8986967 550 9110780 551 9212340 552 9342326 553 9462972 554 9579166 555 9701240 556 9834786 557 9951270 558 10086760 559 10211968 560 10338295 561 10472250 562 10617355 563 10734791 564 10880456 565 11020685 566 11155888 567 11296233 568 11448382 569 11578475 570 11735408 571 11883627 572 12028291 573 12180955 574 12342937 575 12480188 576 12649516 577 12810654 578 12964439 579 13124209 580 13298926 581 13450341 582 13632434 583 13796262 584 13961081 585 14140194 586 14326440 587 14484991 588 14675852 589 14856471 590 15035248 591 15222511 592 15423149 593 15593457 594 15797488 595 15986730 596 16179500 597 16385954 598 16594984 599 16774155 600 16993946 601 17205375 602 17408991 603 17617524 604 17843279 605 18043333 606 18280347 607 18499180 608 18714158 609 18943335 610 19185528 611 19393968 612 19647378 613 19885463 614 20113597 615 20355304 616 20615038 617 20844167 618 21110524 619 21355707 620 21605874 621 21871468 622 22148287 623 22381394 624 22665018 625 22938904 626 23203412 627 23483160 628 23773929 629 24031049 630 24334271 631 24618456 632 24906286 633 25204839 634 25513245 635 25784360 636 26111972 637 26421840 638 26719698 639 27034685 640 27366993 641 27663063 642 28013169 643 28331795 644 28650819 645 28994839 646 29348156 647 29661509 648 30029360 649 30374873 650 30718489 651 31077308 652 31456940 653 31792145 654 32183512 655 32548435 656 32913663 657 33307157 658 33704401 659 34054366 660 34475123 661 34871972 662 35264701 663 35666969 664 36091349 665 36477729 666 36919853 667 37338184 668 37751626 669 38190986 670 38645475 671 39045709 672 39522149 673 39969652 674 40405903 675 40868688 676 41355222 677 41793209 678 42291720 679 42754929 680 43230294 681 43734814 682 44246424 683 44696316 684 45229586 685 45738421 686 46240568 687 46766944 688 47307798 689 47799093 690 48369046 691 48901626 692 49436563 693 49998310 694 50570058 695 51087721 696 51698173 697 52275898 698 52833951 699 53421134 700 54037084 701 54600969 702 55247153 703 55837645 704 56438534 705 57078776 706 57730020 707 58320660 708 58996987 709 59641004 710 60281867 711 60952738 712 61647121 713 62273053 714 62991091 715 63671261 716 64356840 717 65080265 718 65805694 719 66461339 720 67235071 721 67964420 722 68689557 723 69437826 724 70213014 725 70933492 726 71743144 727 72510678 728 73274688 729 74080891 730 74904718 731 75653724 732 76527675 733 77342354 734 78147072 735 78997494 736 79874822 737 80689040 738 81597557 739 82448203 740 83318254 741 84234258 742 85157590 743 85995485 744 86967840 745 87894281 746 88807931 747 89765619 748 90744075 749 91648040 750 92677636 751 93642258 752 94622129 753 95645961 754 96673702 755 97627057 756 98720485 757 99762133 758 100785933 759 101851099 760 102958711 761 103982931 762 105140566 763 106214701 764 107301244 765 108461002 766 109625623 767 110704279 768 111916934 769 113071471 770 114228936 771 115437164 772 116680651 773 117826242 774 119108280 775 120322476 776 121557476 777 122852908 778 124147745 779 125343766 780 126718325 781 128029038 782 129328466 783 130669533 784 132043119 785 133338295 786 134788198 787 136155546 788 137528740 789 138968160 790 140423382 791 141779490 792 143323027 793 144769331 794 146211990 795 147733233 796 149281810 797 150740671 798 152343274 799 153857099 800 155410239 801 157033285 802 158662607 803 160167962 804 161882851 805 163518201 806 165140970 807 166840030 808 168560809 809 170178710 810 171987190 811 173692765 812 175428588 813 177228499 814 179037010 815 180743928 816 182661043 817 184490501 818 186296367 819 188173721 820 190116567 821 191943928 822 193955907 823 195850023 824 197769725 825 199801455 826 201830831 827 203740201 828 205868866 829 207889250 830 209933231 831 212042256 832 214196372 833 216224208 834 218460834 835 220592400 836 222756078 837 225018626 838 227262146 839 229379081 840 231766987 841 234037267 842 236314401 843 238664076 844 241047440 845 243323523 846 245826423 847 248206381 848 250603706 849 253108232 850 255628575 851 258007245 852 260665442 853 263180374 854 265699200 855 268331785 856 271010074 857 273549877 858 276320497 859 278950326 860 281639100 861 284440045 862 287241401 863 289887397 864 292830919 865 295649065 866 298471079 867 301399032 868 304353585 869 307173035 870 310272778 871 313217742 872 316218589 873 319312057 874 322405578 875 325374056 876 328658673 877 331801875 878 334927170 879 338159508 880 341462268 881 344622201 882 348063875 883 351313901 884 354636648 885 358108786 886 361568150 887 364864601 888 368488614 889 371955224 890 375452208 891 379068528 892 382744193 893 386235498 894 390032154 895 393676704 896 397380528 897 401234323 898 405050191 899 408694681 900 412755359 901 416620231 902 420502595 903 424493459 904 428545676 905 432456881 906 436689598 907 440744762 908 444826508 909 449074700 910 453336491 911 457414125 912 461908547 913 466167304 914 470464054 915 474926406 916 479433591 917 483775347 918 488442506 919 492899928 920 497478101 921 502205111 922 506924176 923 511445561 924 516379443 925 521138432 926 525925310 927 530866106 928 535843387 929 540625072 930 545832074 931 550794038 932 555865280 933 561080351 934 566277228 935 571325086 936 576806204 937 582078864 938 587362818 939 592806948 940 598346660 941 603678273 942 609432198 943 614910090 944 620484213 945 626289172 946 632083472 947 637654698 948 643712826 949 649523772 950 655386641 951 661448722 952 667561912 953 673448050 954 679783239 955 685872955 956 692096027 957 698504326 958 704861987 959 711011974 960 717743114 961 724198516 962 730694932 963 737359453 964 744078404 965 750644973 966 757665238 967 764391490 968 771246166 969 778305868 970 785369596 971 792204193 972 799630619 973 806720071 974 813876456 975 821284914 976 828754780 977 836000269 978 843708170 979 851129194 980 858728896 981 866538333 982 874361405 983 881888766 984 890035794 985 897925280 986 905851718 987 914022163 988 922226751 989 930212716 990 938768562 991 946986965 992 955374018 993 963955176 994 972534153 995 980911487 996 989947878 997 998630900 998 1007359739 999 1016341657 1000 1025424141