1 1 2 2 3 4 4 4 5 6 6 9 7 8 8 10 9 14 10 13 11 16 12 21 13 17 14 22 15 28 16 23 17 30 18 37 19 30 20 38 21 46 22 38 23 46 24 59 25 46 26 55 27 70 28 59 29 70 30 86 31 67 32 81 33 96 34 84 35 98 36 115 37 95 38 114 39 135 40 114 41 132 42 158 43 127 44 156 45 178 46 148 47 176 48 207 49 172 50 201 51 227 52 196 53 228 54 270 55 222 56 255 57 296 58 255 59 295 60 338 61 278 62 327 63 371 64 326 65 366 66 414 67 357 68 412 69 465 70 405 71 453 72 516 73 441 74 517 75 568 76 494 77 564 78 635 79 548 80 626 81 688 82 614 83 684 84 778 85 671 86 748 87 836 88 750 89 839 90 926 91 807 92 911 93 994 94 907 95 1005 96 1099 97 979 98 1099 99 1200 100 1080 101 1187 102 1315 103 1170 104 1320 105 1419 106 1279 107 1419 108 1548 109 1402 110 1552 111 1658 112 1525 113 1672 114 1831 115 1644 116 1816 117 1964 118 1802 119 1981 120 2134 121 1920 122 2132 123 2288 124 2129 125 2305 126 2471 127 2268 128 2493 129 2669 130 2472 131 2675 132 2886 133 2646 134 2915 135 3078 136 2852 137 3122 138 3339 139 3085 140 3359 141 3545 142 3320 143 3593 144 3861 145 3557 146 3852 147 4103 148 3849 149 4152 150 4407 151 4084 152 4449 153 4692 154 4441 155 4753 156 5020 157 4711 158 5114 159 5398 160 5078 161 5424 162 5756 163 5399 164 5850 165 6127 166 5785 167 6217 168 6562 169 6192 170 6637 171 6925 172 6612 173 7071 174 7473 175 7039 176 7528 177 7891 178 7530 179 8053 180 8434 181 7965 182 8553 183 8924 184 8563 185 9088 186 9505 187 9056 188 9691 189 10109 190 9657 191 10236 192 10732 193 10241 194 10962 195 11358 196 10877 197 11572 198 12073 199 11560 200 12307 201 12744 202 12289 203 13030 204 13606 205 12987 206 13778 207 14331 208 13825 209 14647 210 15214 211 14563 212 15482 213 16033 214 15540 215 16377 216 16974 217 16363 218 17352 219 17965 220 17356 221 18285 222 19001 223 18297 224 19412 225 20003 226 19347 227 20426 228 21189 229 20490 230 21613 231 22266 232 21637 233 22747 234 23582 235 22795 236 24019 237 24809 238 24132 239 25371 240 26173 241 25336 242 26739 243 27529 244 26857 245 28134 246 29002 247 28212 248 29684 249 30575 250 29775 251 31166 252 32181 253 31288 254 32921 255 33768 256 32969 257 34585 258 35616 259 34717 260 36389 261 37289 262 36525 263 38237 264 39404 265 38363 266 40170 267 41269 268 40402 269 42254 270 43403 271 42341 272 44379 273 45508 274 44651 275 46544 276 47752 277 46770 278 48936 279 50154 280 49155 281 51233 282 52629 283 51533 284 53936 285 55131 286 54073 287 56420 288 57865 289 56733 290 59188 291 60522 292 59568 293 62014 294 63624 295 62321 296 64947 297 66456 298 65438 299 68116 300 69691 301 68394 302 71325 303 72883 304 71833 305 74612 306 76308 307 75075 308 78162 309 79886 310 78647 311 81635 312 83602 313 82267 314 85611 315 87296 316 86060 317 89386 318 91383 319 90101 320 93554 321 95336 322 94204 323 97709 324 99877 325 98372 326 102127 327 104207 328 102984 329 106762 330 108911 331 107361 332 111476 333 113634 334 112461 335 116357 336 118667 337 117257 338 121591 339 123904 340 122539 341 126759 342 129332 343 127800 344 132517 345 134819 346 133415 347 138130 348 140813 349 139257 350 144108 351 146589 352 145298 353 150221 354 153170 355 151453 356 156639 357 159455 358 158056 359 163344 360 166241 361 164567 362 170277 363 173135 364 171817 365 177296 366 180389 367 178804 368 184893 369 188008 370 186420 371 192322 372 195816 373 194069 374 200567 375 203734 376 202156 377 208611 378 212244 379 210550 380 217238 381 220626 382 219286 383 226075 384 229964 385 228021 386 235173 387 238958 388 237467 389 244802 390 248740 391 246837 392 254612 393 258543 394 257107 395 264636 396 268878 397 267205 398 275357 399 279581 400 277960 401 285992 402 290643 403 288882 404 297690 405 301885 406 300313 407 309102 408 313906 409 312146 410 321312 411 325864 412 324444 413 333673 414 338867 415 336860 416 346571 417 351702 418 350242 419 360065 420 365302 421 363378 422 373842 423 379086 424 377809 425 388035 426 393607 427 391968 428 403005 429 408581 430 406967 431 417959 432 424134 433 422332 434 434119 435 439802 436 438303 437 450118 438 456582 439 454878 440 467058 441 473151 442 471943 443 484332 444 491202 445 489359 446 502375 447 509078 448 507776 449 520986 450 527893 451 526108 452 540197 453 547187 454 546015 455 559737 456 567177 457 565667 458 580380 459 587929 460 586576 461 601112 462 609260 463 607718 464 623285 465 630885 466 629775 467 645490 468 653919 469 652560 470 668759 471 676861 472 676101 473 692628 474 701635 475 699968 476 717176 477 726076 478 725259 479 742714 480 751982 481 750655 482 769073 483 778314 484 777704 485 795807 486 805578 487 804753 488 824135 489 833903 490 833114 491 852423 492 863018 493 862049 494 882673 495 892691 496 892128 497 912828 498 923911 499 923149 500 944472 501 955275 502 955233 503 976860 504 988640 505 987717 506 1010269 507 1021937 508 1022086 509 1045031 510 1057009 511 1056420 512 1080582 513 1092648 514 1093032 515 1116955 516 1129747 517 1129693 518 1155026 519 1167877 520 1168009 521 1193319 522 1207234 523 1207273 524 1234032 525 1247205 526 1247773 527 1274799 528 1289202 529 1289588 530 1317426 531 1331442 532 1332645 533 1360969 534 1376258 535 1376489 536 1406068 537 1421299 538 1422525 539 1452392 540 1468098 541 1468742 542 1500091 543 1516070 544 1517889 545 1548876 546 1565604 547 1566989 548 1599798 549 1616562 550 1618395 551 1651274 552 1669180 553 1670768 554 1705402 555 1722622 556 1724899 557 1760008 558 1778733 559 1780756 560 1816737 561 1835133 562 1838201 563 1874845 564 1894763 565 1896754 566 1934724 567 1954512 568 1957891 569 1996448 570 2016854 571 2019679 572 2060037 573 2080596 574 2084537 575 2124643 576 2146314 577 2149938 578 2192297 579 2214097 580 2218070 581 2260466 582 2283678 583 2287513 584 2332006 585 2354568 586 2359434 587 2404340 588 2428569 589 2433176 590 2479369 591 2503251 592 2509196 593 2556239 594 2581713 595 2586466 596 2635249 597 2660803 598 2667129 599 2716753 600 2743111 601 2748640 602 2800277 603 2826946 604 2834056 605 2885542 606 2913612 607 2920418 608 2974353 609 3002516 610 3009814 611 3064075 612 3093939 613 3101380 614 3158183 615 3187205 616 3195633 617 3253034 618 3284169 619 3292356 620 3351471 621 3382370 622 3392086 623 3452064 624 3484958 625 3493519 626 3555626 627 3588688 628 3599133 629 3662046 630 3695953 631 3705833 632 3771387 633 3805727 634 3817495 635 3883092 636 3918950 637 3930192 638 3998716 639 4034861 640 4046925 641 4116137 642 4154383 643 4166388 644 4238345 645 4275777 646 4289193 647 4362092 648 4402093 649 4415443 650 4490169 651 4529876 652 4545082 653 4621121 654 4663119 655 4677115 656 4755831 657 4797962 658 4814136 659 4893949 660 4937391 661 4952978 662 5036005 663 5080061 664 5097613 665 5180589 666 5226544 667 5244040 668 5330590 669 5377082 670 5395563 671 5482760 672 5531465 673 5550011 674 5640705 675 5688681 676 5709233 677 5801240 678 5851974 679 5872236 680 5966616 681 6017332 682 6039721 683 6135838 684 6189318 685 6210422 686 6309548 687 6363446 688 6387296 689 6487782 690 6543353 691 6566691 692 6670802 693 6726952 694 6752801 695 6857269 696 6915806 697 6941768 698 7050507 699 7109439 700 7136370 701 7246178 702 7308085 703 7335432 704 7449425 705 7510684 706 7540040 707 7655418 708 7720045 709 7749452 710 7867746 711 7932579 712 7964839 713 8085085 714 8152932 715 8183894 716 8307950 717 8376362 718 8410568 719 8536521 720 8606794 721 8640511 722 8770821 723 8842212 724 8878840 725 9009892 726 9084160 727 9120703 728 9256504 729 9331469 730 9369866 731 9507145 732 9585750 733 9624672 734 9766561 735 9844382 736 9885850 737 10029846 738 10111597 739 10153484 740 10301127 741 10383140 742 10428092 743 10578231 744 10663920 745 10707674 746 10862524 747 10949154 748 10996613 749 11153455 750 11242436 751 11289852 752 11451910 753 11542397 754 11593162 755 11756111 756 11849855 757 11901132 758 12070001 759 12164627 760 12218091 761 12388967 762 12487581 763 12541528 764 12718052 765 12816287 766 12873603 767 13052882 768 13155971 769 13213438 770 13396724 771 13500378 772 13561810 773 13748182 774 13856334 775 13916891 776 14108670 777 14217838 778 14282827 779 14477404 780 14589397 781 14654601 782 14855451 783 14969090 784 15038264 785 15240586 786 15358423 787 15428330 788 15637581 789 15756736 790 15828931 791 16040607 792 16164611 793 16238249 794 16456426 795 16580416 796 16658089 797 16879433 798 17008648 799 17086824 800 17313525 801 17443639 802 17526822 803 17757461 804 17892583 805 17974558 806 18211692 807 18348582 808 18435789 809 18676479 810 18816972 811 18904604 812 19152499 813 19295267 814 19387773 815 19637526 816 19785351 817 19879045 818 20136783 819 20286070 820 20383099 821 20644267 822 20799289 823 20898269 824 21167118 825 21322024 826 21425325 827 21698332 828 21859792 829 21964331 830 22243819 831 22406786 832 22516729 833 22800704 834 22969687 835 23078985 836 23370724 837 23542009 838 23657787 839 23953580 840 24129095 841 24245721 842 24550331 843 24728537 844 24851020 845 25158465 846 25342457 847 25466427 848 25783382 849 25969673 850 26097690 851 26419008 852 26612165 853 26742181 854 27072158 855 27265894 856 27401885 857 27737046 858 27938530 859 28076213 860 28418585 861 28621861 862 28766110 863 29114527 864 29324646 865 29469051 866 29826728 867 30039653 868 30191168 869 30553988 870 30772281 871 30925088 872 31298520 873 31520491 874 31680073 875 32056768 876 32285826 877 32447815 878 32835675 879 33067679 880 33234675 881 33627541 882 33867328 883 34037485 884 34441173 885 34682098 886 34859315 887 35269240 888 35518888 889 35697941 890 36116836 891 36369373 892 36556427 893 36982637 894 37243486 895 37430869 896 37867518 897 38132081 898 38328154 899 38771303 900 39042521 901 39241106 902 39696006 903 39971403 904 40178040 905 40637756 906 40921457 907 41131379 908 41604361 909 41891376 910 42107417 911 42586927 912 42883707 913 43103507 914 43595673 915 43894162 916 44122026 917 44621504 918 44930515 919 45161670 920 45671952 921 45984879 922 46225491 923 46744068 924 47066323 925 47307930 926 47839422 927 48166441 928 48418784 929 48958286 930 49292847 931 49548085 932 50101541 933 50441856 934 50706383 935 51266298 936 51616573 937 51885325 938 52460032 939 52815083 940 53091668 941 53674401 942 54040653 943 54322170 944 54919349 945 55287956 946 55579672 947 56186249 948 56567088 949 56863049 950 57482651 951 57867998 952 58174649 953 58804542 954 59201386 955 59510275 956 60155631 957 60558485 958 60879198 959 61533532 960 61945873 961 62271073 962 62941965 963 63361418 964 63698124 965 64376584 966 64807587 967 65149762 968 65845941 969 66282616 970 66634225 971 67340608 972 67790239 973 68148073 974 68871428 975 69325037 976 69694863 977 70429698 978 70897610 979 71272157 980 72021946 981 72496003 982 72884361 983 73646508 984 74134176 985 74525814 986 75305591 987 75800193 988 76205997 989 76997386 990 77503317 991 77915415 992 78726328 993 79240548 994 79665489 995 80486048 996 81014370 997 81446228 998 82287753 999 82823450 1000 83266488