1 0 2 0 3 1 4 1 5 1 6 1 7 1 8 1 9 2 10 1 11 1 12 3 13 2 14 2 15 4 16 3 17 3 18 6 19 4 20 4 21 7 22 6 23 6 24 9 25 7 26 7 27 11 28 9 29 9 30 15 31 11 32 11 33 18 34 15 35 15 36 22 37 18 38 18 39 27 40 23 41 22 42 33 43 28 44 28 45 41 46 34 47 34 48 49 49 42 50 42 51 56 52 51 53 51 54 68 55 60 56 59 57 79 58 72 59 71 60 94 61 83 62 84 63 111 64 100 65 100 66 127 67 117 68 118 69 147 70 136 71 135 72 171 73 158 74 158 75 199 76 183 77 183 78 229 79 213 80 214 81 260 82 246 83 247 84 301 85 282 86 282 87 342 88 325 89 326 90 392 91 368 92 372 93 448 94 422 95 425 96 505 97 481 98 486 99 573 100 546 101 547 102 649 103 619 104 622 105 734 106 698 107 704 108 829 109 789 110 796 111 924 112 891 113 898 114 1040 115 999 116 1004 117 1165 118 1123 119 1129 120 1305 121 1253 122 1264 123 1459 124 1406 125 1416 126 1623 127 1571 128 1586 129 1809 130 1753 131 1762 132 2010 133 1952 134 1965 135 2233 136 2166 137 2184 138 2482 139 2408 140 2427 141 2737 142 2675 143 2696 144 3034 145 2959 146 2979 147 3355 148 3281 149 3302 150 3702 151 3617 152 3653 153 4087 154 3996 155 4030 156 4495 157 4411 158 4452 159 4948 160 4859 161 4894 162 5442 163 5348 164 5390 165 5975 166 5873 167 5926 168 6564 169 6450 170 6512 171 7181 172 7082 173 7150 174 7869 175 7758 176 7827 177 8612 178 8500 179 8574 180 9419 181 9288 182 9384 183 10293 184 10161 185 10257 186 11221 187 11103 188 11216 189 12244 190 12113 191 12225 192 13349 193 13213 194 13339 195 14525 196 14387 197 14536 198 15821 199 15662 200 15823 201 17183 202 17051 203 17225 204 18672 205 18527 206 18709 207 20278 208 20135 209 20327 210 22005 211 21842 212 22076 213 23863 214 23702 215 23947 216 25840 217 25700 218 25972 219 27984 220 27844 221 28117 222 30293 223 30148 224 30452 225 32754 226 32606 227 32952 228 35421 229 35260 230 35632 231 38235 232 38124 233 38528 234 41286 235 41160 236 41591 237 44555 238 44445 239 44897 240 48047 241 47923 242 48451 243 51801 244 51679 245 52232 246 55775 247 55703 248 56309 249 60047 250 59992 251 60618 252 64639 253 64580 254 65267 255 69512 256 69468 257 70232 258 74744 259 74702 260 75529 261 80285 262 80312 263 81197 264 86240 265 86270 266 87205 267 92580 268 92657 269 93648 270 99341 271 99412 272 100531 273 106567 274 106659 275 107840 276 114202 277 114386 278 115676 279 122370 280 122595 281 123934 282 131103 283 131351 284 132790 285 140342 286 140635 287 142223 288 150225 289 150533 290 152229 291 160652 292 161106 293 162911 294 171792 295 172286 296 174208 297 183640 298 184211 299 186245 300 196207 301 196816 302 199057 303 209576 304 210260 305 212627 306 223710 307 224537 308 227093 309 238740 310 239675 311 242344 312 254722 313 255749 314 258601 315 271623 316 272748 317 275855 318 289608 319 290802 320 294115 321 308551 322 310000 323 313520 324 328715 325 330261 326 333991 327 350091 328 351803 329 355732 330 372665 331 374507 332 378804 333 396627 334 398614 335 403145 336 421901 337 424160 338 429013 339 448669 340 451147 341 456246 342 477056 343 479718 344 485134 345 506999 346 509877 347 515709 348 538736 349 541789 350 547995 351 572134 352 575597 353 582172 354 607523 355 611228 356 618180 357 644931 358 648947 359 656279 360 684376 361 688650 362 696581 363 726085 364 730676 365 739018 366 769998 367 775065 368 783959 369 816396 370 821836 371 831193 372 865438 373 871252 374 881136 375 917016 376 923280 377 933871 378 971563 379 978166 380 989393 381 1028869 382 1036163 383 1048021 384 1089366 385 1097144 386 1109666 387 1153195 388 1161517 389 1174682 390 1220350 391 1229179 392 1243305 393 1291131 394 1300563 395 1315432 396 1365552 397 1375776 398 1391537 399 1443955 400 1454894 401 1471457 402 1526595 403 1538217 404 1555706 405 1613402 406 1625793 407 1644412 408 1704916 409 1717988 410 1737642 411 1800916 412 1815126 413 1835852 414 1902010 415 1917068 416 1938926 417 2008406 418 2024445 419 2047377 420 2120109 421 2137093 422 2161574 423 2237625 424 2255620 425 2281354 426 2360937 427 2380274 428 2407440 429 2490531 430 2511111 431 2539639 432 2626872 433 2648599 434 2678638 435 2769807 436 2792885 437 2824720 438 2920077 439 2944410 440 2977970 441 3077565 442 3103672 443 3138979 444 3243001 445 3270604 446 3307745 447 3416700 448 3445986 449 3484916 450 3598822 451 3629697 452 3671028 453 3790002 454 3822595 455 3865980 456 3990253 457 4025043 458 4070738 459 4200308 460 4237154 461 4285076 462 4420832 463 4459648 464 4509980 465 4651628 466 4692703 467 4745899 468 4893815 469 4936984 470 4992902 471 5147252 472 5193279 473 5251947 474 5412915 475 5461444 476 5523102 477 5691383 478 5742614 479 5807159 480 5982837 481 6036773 482 6104985 483 6288180 484 6344990 485 6416527 486 6607621 487 6667846 488 6743021 489 6942068 490 7005650 491 7084356 492 7292462 493 7359325 494 7441836 495 7658754 496 7729208 497 7816144 498 8042350 499 8116275 500 8207493 501 8443177 502 8521609 503 8617175 504 8862674 505 8945106 506 9045357 507 9301637 508 9388402 509 9493191 510 9760298 511 9851493 512 9961915 513 10240119 514 10335850 515 10451449 516 10741383 517 10842459 518 10963646 519 11265259 520 11371683 521 11498470 522 11813248 523 11924879 524 12057561 525 12385331 526 12502667 527 12642068 528 12983376 529 13106307 530 13252357 531 13607568 532 13737363 533 13890106 534 14259761 535 14395922 536 14555829 537 14941123 538 15084069 539 15251072 540 15652170 541 15802048 542 15977529 543 16394806 544 16551902 545 16735311 546 17169601 547 17334948 548 17526923 549 17978263 550 18151801 551 18352420 552 18822814 553 19004526 554 19214071 555 19703308 556 19893943 557 20113625 558 20622489 559 20821787 560 21051588 561 21580669 562 21790413 563 22030362 564 22580256 565 22799956 566 23050812 567 23623215 568 23853270 569 24114949 570 24710237 571 24951007 572 25225303 573 25843844 574 26095788 575 26382148 576 27025233 577 27289594 578 27588759 579 28256595 580 28533499 581 28845709 582 29540676 583 29830160 584 30155940 585 30877978 586 31180988 587 31521810 588 32272088 589 32588441 590 32944375 591 33723638 592 34055650 593 34426887 594 35235981 595 35583064 596 35970606 597 36811899 598 37174683 599 37578405 600 38452404 601 38831492 602 39253872 603 40161094 604 40557015 605 40997444 606 41939728 607 42354285 608 42813654 609 43791259 610 44224712 611 44703611 612 45719724 613 46172012 614 46671094 615 47725872 616 48198505 617 48719630 618 49814482 619 50307336 620 50850862 621 51987013 622 52502859 623 53069056 624 54247710 625 54786203 626 55376412 627 56600430 628 57162501 629 57776762 630 59047136 631 59633440 632 60274923 633 61592500 634 62203908 635 62872010 636 64239102 637 64878076 638 65573996 639 66991198 640 67658086 641 68382718 642 69854222 643 70549148 644 71303393 645 72829387 646 73554495 647 74340929 648 75923356 649 76678461 650 77497612 651 79138432 652 79927211 653 80779470 654 82480130 655 83302373 656 84189831 657 85954102 658 86810919 659 87733584 660 89563157 661 90455760 662 91417605 663 93313507 664 94243145 665 95243909 666 97209234 667 98178936 668 99220160 669 101255988 670 102266612 671 103349500 672 105461080 673 106512947 674 107638942 675 109826919 676 110922662 677 112095099 678 114362108 679 115501908 680 116721586 681 119070238 682 120258845 683 121526502 684 123958958 685 125196165 686 126514656 687 129035809 688 130323388 689 131692826 690 134304831 691 135644702 692 137070330 693 139774868 694 141168393 695 142650149 696 145451602 697 146902895 698 148442744 699 151342405 700 152853014 701 154452924 702 157457655 703 159027920 704 160689761 705 163800972 706 165434575 707 167162687 708 170383498 709 172081112 710 173876979 711 177211071 712 178978555 713 180843171 714 184293796 715 186131346 716 188068546 717 191641793 718 193551832 719 195562256 720 199261289 721 201246418 722 203336533 723 207163943 724 209226352 725 211396432 726 215357787 727 217502813 728 219755803 729 223853060 730 226082807 731 228421457 732 232663563 733 234978992 734 237405667 735 241794733 736 244200802 737 246721437 738 251261668 739 253759194 740 256376061 741 261072676 742 263669442 743 266383771 744 271240980 745 273937866 746 276755041 747 281780857 748 284580753 749 287501952 750 292700864 751 295607780 752 298641151 753 304016425 754 307033552 755 310180132 756 315739426 757 318873277 758 322136906 759 327883336 760 331137253 761 334521778 762 340466331 763 343842043 764 347350981 765 353497140 766 357000893 767 360641713 768 366995390 769 370628885 770 374404937 771 380972665 772 384746044 773 388659507 774 395447022 775 399361756 776 403419655 777 410437700 778 414497778 779 418701943 780 425956493 781 430167586 782 434528685 783 442024246 784 446390534 785 450910387 786 458657405 787 463187583 788 467871091 789 475873728 790 480572668 791 485425687 792 493697876 793 498567926 794 503595129 795 512142236 796 517192092 797 522402891 798 531232497 799 536464825 800 541864508 801 550985590 802 556412796 803 562004459 804 571424995 805 577050211 806 582842816 807 592576231 808 598405099 809 604401912 810 614456605 811 620496272 812 626710901 813 637093244 814 643349885 815 649785295 816 660508524 817 666993651 818 673656534 819 684726912 820 691446838 821 698345251 822 709780695 823 716739174 824 723879446 825 735687177 826 742895994 827 750290413 828 762480681 829 769943500 830 777599355 831 790184597 832 797917419 833 805839163 834 818829358 835 826837403 836 835037321 837 848449742 838 856740212 839 865222883 840 879069569 841 887652393 842 896434926 843 910724130 844 919607874 845 928695562 846 943444514 847 952643648 848 962045168 849 977263175 850 986786866 851 996512814 852 1012222211 853 1022076126 854 1032135707 855 1048346569 856 1058545769 857 1068954729 858 1085680774 859 1096231286 860 1106999433 861 1124256982 862 1135179018 863 1146313187 864 1164115811 865 1175416616 866 1186932838 867 1205302797 868 1216992689 869 1228897328 870 1247850419 871 1259943005 872 1272258165 873 1291805832 874 1304312008 875 1317045693 876 1337210549 877 1350149465 878 1363312896 879 1384107140 880 1397491832 881 1411099679 882 1432551904 883 1446389640 884 1460454329 885 1482579062 886 1496889780 887 1511431349 888 1534245905 889 1549038936 890 1564071095 891 1587597220 892 1602897625 893 1618429818 894 1642686075 895 1658504630 896 1674557772 897 1699571789 898 1715922696 899 1732506509 900 1758299479 901 1775200468 902 1792342546 903 1818930665 904 1836396719 905 1854108599 906 1881520449 907 1899576283 908 1917873552 909 1946125861 910 1964788747 911 1983690571 912 2012820148 913 2032100946 914 2051623611 915 2081649828 916 2101574676 917 2121744684 918 2152689972 919 2173271501 920 2194107449 921 2226000795 922 2247271270 923 2268785699 924 2301651328 925 2323626241 926 2345846978 927 2379720249 928 2402417654 929 2425358500 930 2460267812 931 2483711979 932 2507407286 933 2543373872 934 2567585258 935 2592051861 936 2629112842 937 2654122273 938 2679380861 939 2717559114 940 2743390566 941 2769466297 942 2808807403 943 2835476540 944 2862391718 945 2902922484 946 2930462002 947 2958250400 948 3000000875 949 3028428931 950 3057115319 951 3100122233 952 3129480358 953 3159082476 954 3203377940 955 3233686979 956 3264240657 957 3309870401 958 3341154575 959 3372678916 960 3419679363 961 3451971277 962 3484510274 963 3532909681 964 3566236013 965 3599812786 966 3649659797 967 3684060125 968 3718701688 969 3770026353 970 3805532943 971 3841273308 972 3894132928 973 3930766950 974 3967635236 975 4022066570 976 4059870862 977 4097909741 978 4153951228 979 4192950933 980 4232194646 981 4289893710 982 4330140551 983 4370613052 984 4430012448 985 4471535939 986 4513282686 987 4574439930 988 4617272331 989 4660320624 990 4723283508 991 4767466343 992 4811871752 993 4876678281 994 4922247866 995 4968041231 996 5034753096 997 5081760545 998 5128977967 999 5197635507 1000 5246122439