0 1 1 0 2 0 3 1 4 1 5 0 6 1 7 1 8 2 9 2 10 1 11 2 12 4 13 2 14 2 15 4 16 5 17 4 18 5 19 5 20 7 21 7 22 6 23 7 24 11 25 9 26 9 27 12 28 13 29 12 30 14 31 14 32 17 33 18 34 17 35 19 36 24 37 21 38 22 39 26 40 28 41 27 42 30 43 31 44 35 45 36 46 35 47 38 48 45 49 42 50 43 51 49 52 52 53 51 54 55 55 56 56 62 57 64 58 63 59 67 60 76 61 73 62 75 63 82 64 86 65 86 66 91 67 93 68 100 69 103 70 103 71 108 72 119 73 116 74 119 75 128 76 133 77 133 78 140 79 143 80 152 81 156 82 156 83 163 84 176 85 173 86 177 87 188 88 195 89 196 90 204 91 208 92 219 93 224 94 225 95 233 96 249 97 247 98 252 99 265 100 273 101 275 102 285 103 290 104 303 105 310 106 312 107 322 108 340 109 338 110 345 111 360 112 370 113 373 114 385 115 392 116 407 117 415 118 418 119 430 120 451 121 450 122 458 123 476 124 488 125 492 126 506 127 514 128 532 129 542 130 546 131 560 132 584 133 584 134 594 135 614 136 628 137 634 138 650 139 660 140 680 141 692 142 698 143 714 144 741 145 742 146 754 147 777 148 793 149 800 150 819 151 831 152 854 153 868 154 875 155 894 156 924 157 926 158 940 159 966 160 985 161 994 162 1015 163 1029 164 1055 165 1071 166 1080 167 1101 168 1135 169 1139 170 1155 171 1184 172 1205 173 1216 174 1240 175 1256 176 1285 177 1304 178 1315 179 1339 180 1376 181 1381 182 1400 183 1432 184 1456 185 1469 186 1496 187 1515 188 1547 189 1568 190 1581 191 1608 192 1649 193 1656 194 1677 195 1713 196 1740 197 1755 198 1785 199 1806 200 1842 201 1866 202 1881 203 1911 204 1956 205 1965 206 1989 207 2028 208 2058 209 2076 210 2109 211 2133 212 2172 213 2199 214 2217 215 2250 216 2299 217 2310 218 2337 219 2380 220 2413 221 2433 222 2470 223 2497 224 2540 225 2570 226 2590 227 2627 228 2680 229 2693 230 2723 231 2770 232 2807 233 2830 234 2870 235 2900 236 2947 237 2980 238 3003 239 3043 240 3101 241 3117 242 3150 243 3201 244 3241 245 3267 246 3311 247 3344 248 3395 249 3432 250 3458 251 3502 252 3564 253 3582 254 3619 255 3674 256 3718 257 3747 258 3795 259 3832 260 3887 261 3927 262 3956 263 4004 264 4071 265 4092 266 4132 267 4192 268 4240 269 4272 270 4324 271 4364 272 4424 273 4468 274 4500 275 4552 276 4624 277 4648 278 4692 279 4756 280 4808 281 4844 282 4900 283 4944 284 5008 285 5056 286 5092 287 5148 288 5225 289 5252 290 5300 291 5369 292 5425 293 5464 294 5525 295 5573 296 5642 297 5694 298 5733 299 5794 300 5876 301 5906 302 5958 303 6032 304 6093 305 6136 306 6201 307 6253 308 6327 309 6383 310 6426 311 6491 312 6579 313 6613 314 6669 315 6748 316 6813 317 6860 318 6930 319 6986 320 7065 321 7126 322 7173 323 7243 324 7336 325 7373 326 7434 327 7518 328 7588 329 7639 330 7714 331 7775 332 7859 333 7924 334 7975 335 8050 336 8149 337 8190 338 8255 339 8345 340 8420 341 8475 342 8555 343 8620 344 8710 345 8780 346 8835 347 8915 348 9020 349 9065 350 9135 351 9230 352 9310 353 9370 354 9455 355 9525 356 9620 357 9695 358 9755 359 9840 360 9951 361 10000 362 10075 363 10176 364 10261 365 10325 366 10416 367 10491 368 10592 369 10672 370 10736 371 10827 372 10944 373 10997 374 11077 375 11184 376 11275 377 11344 378 11440 379 11520 380 11627 381 11712 382 11781 383 11877 384 12001 385 12059 386 12144 387 12257 388 12353 389 12427 390 12529 391 12614 392 12727 393 12818 394 12892 395 12994 396 13124 397 13186 398 13277 399 13396 400 13498 401 13577 402 13685 403 13776 404 13895 405 13991 406 14070 407 14178 408 14315 409 14382 410 14478 411 14604 412 14712 413 14796 414 14910 415 15006 416 15132 417 15234 418 15318 419 15432 420 15576 421 15648 422 15750 423 15882 424 15996 425 16086 426 16206 427 16308 428 16440 429 16548 430 16638 431 16758 432 16909 433 16986 434 17094 435 17233 436 17353 437 17448 438 17575 439 17683 440 17822 441 17936 442 18031 443 18158 444 18316 445 18398 446 18512 447 18658 448 18785 449 18886 450 19019 451 19133 452 19279 453 19399 454 19500 455 19633 456 19799 457 19887 458 20007 459 20160 460 20293 461 20400 462 20540 463 20660 464 20813 465 20940 466 21047 467 21187 468 21360 469 21453 470 21580 471 21740 472 21880 473 21993 474 22140 475 22267 476 22427 477 22560 478 22673 479 22820 480 23001 481 23100 482 23233 483 23401 484 23548 485 23667 486 23821 487 23954 488 24122 489 24262 490 24381 491 24535 492 24724 493 24829 494 24969 495 25144 496 25298 497 25424 498 25585 499 25725 500 25900 501 26047 502 26173 503 26334 504 26531 505 26642 506 26789 507 26972 508 27133 509 27265 510 27434 511 27581 512 27764 513 27918 514 28050 515 28219 516 28424 517 28541 518 28695 519 28886 520 29055 521 29194 522 29370 523 29524 524 29715 525 29876 526 30015 527 30191 528 30405 529 30529 530 30690 531 30889 532 31065 533 31211 534 31395 535 31556 536 31755 537 31924 538 32070 539 32254 540 32476 541 32606 542 32775 543 32982 544 33166 545 33319 546 33511 547 33680 548 33887 549 34063 550 34216 551 34408 552 34639 553 34776 554 34952 555 35168 556 35360 557 35520 558 35720 559 35896 560 36112 561 36296 562 36456 563 36656 564 36896 565 37040 566 37224 567 37448 568 37648 569 37816 570 38024 571 38208 572 38432 573 38624 574 38792 575 39000 576 39249 577 39400 578 39592 579 39825 580 40033 581 40208 582 40425 583 40617 584 40850 585 41050 586 41225 587 41442 588 41700 589 41858 590 42058 591 42300 592 42517 593 42700 594 42925 595 43125 596 43367 597 43575 598 43758 599 43983 600 44251 601 44417 602 44625 603 44876 604 45101 605 45292 606 45526 607 45734 608 45985 609 46202 610 46393 611 46627 612 46904 613 47077 614 47294 615 47554 616 47788 617 47987 618 48230 619 48447 620 48707 621 48932 622 49131 623 49374 624 49661 625 49842 626 50067 627 50337 628 50580 629 50787 630 51039 631 51264 632 51534 633 51768 634 51975 635 52227 636 52524 637 52713 638 52947 639 53226 640 53478 641 53694 642 53955 643 54189 644 54468 645 54711 646 54927 647 55188 648 55495 649 55692 650 55935 651 56224 652 56485 653 56709 654 56980 655 57223 656 57512 657 57764 658 57988 659 58259 660 58576 661 58781 662 59033 663 59332 664 59603 665 59836 666 60116 667 60368 668 60667 669 60928 670 61161 671 61441 672 61769 673 61983 674 62244 675 62553 676 62833 677 63075 678 63365 679 63626 680 63935 681 64206 682 64448 683 64738 684 65076 685 65298 686 65569 687 65888 688 66178 689 66429 690 66729 691 67000 692 67319 693 67599 694 67850 695 68150 696 68499 697 68730 698 69010 699 69340 700 69640 701 69900 702 70210 703 70490 704 70820 705 71110 706 71370 707 71680 708 72040 709 72280 710 72570 711 72910 712 73220 713 73490 714 73810 715 74100 716 74440 717 74740 718 75010 719 75330 720 75701 721 75950 722 76250 723 76601 724 76921 725 77200 726 77531 727 77831 728 78182 729 78492 730 78771 731 79102 732 79484 733 79742 734 80052 735 80414 736 80745 737 81034 738 81375 739 81685 740 82047 741 82367 742 82656 743 82997 744 83391 745 83659 746 83979 747 84352 748 84693 749 84992 750 85344 751 85664 752 86037 753 86368 754 86667 755 87019 756 87424 757 87701 758 88032 759 88416 760 88768 761 89077 762 89440 763 89771 764 90155 765 90496 766 90805 767 91168 768 91585 769 91872 770 92213 771 92609 772 92972 773 93291 774 93665 775 94006 776 94402 777 94754 778 95073 779 95447 780 95876 781 96173 782 96525 783 96932 784 97306 785 97636 786 98021 787 98373 788 98780 789 99143 790 99473 791 99858 792 100299 793 100606 794 100969 795 101388 796 101773 797 102113 798 102510 799 102873 800 103292 801 103666 802 104006 803 104403 804 104856 805 105173 806 105547 807 105978 808 106375 809 106726 810 107134 811 107508 812 107939 813 108324 814 108675 815 109083 816 109549 817 109877 818 110262 819 110705 820 111113 821 111475 822 111895 823 112280 824 112723 825 113120 826 113482 827 113902 828 114380 829 114718 830 115115 831 115570 832 115990 833 116363 834 116795 835 117192 836 117647 837 118055 838 118428 839 118860 840 119351 841 119700 842 120108 843 120576 844 121008 845 121392 846 121836 847 122244 848 122712 849 123132 850 123516 851 123960 852 124464 853 124824 854 125244 855 125724 856 126168 857 126564 858 127020 859 127440 860 127920 861 128352 862 128748 863 129204 864 129721 865 130092 866 130524 867 131017 868 131473 869 131880 870 132349 871 132781 872 133274 873 133718 874 134125 875 134594 876 135124 877 135506 878 135950 879 136456 880 136925 881 137344 882 137825 883 138269 884 138775 885 139231 886 139650 887 140131 888 140675 889 141069 890 141525 891 142044 892 142525 893 142956 894 143450 895 143906 896 144425 897 144894 898 145325 899 145819 900 146376 901 146781 902 147250 903 147782 904 148276 905 148719 906 149226 907 149695 908 150227 909 150708 910 151151 911 151658 912 152229 913 152646 914 153127 915 153673 916 154180 917 154635 918 155155 919 155636 920 156182 921 156676 922 157131 923 157651 924 158236 925 158665 926 159159 927 159718 928 160238 929 160706 930 161239 931 161733 932 162292 933 162799 934 163267 935 163800 936 164399 937 164840 938 165347 939 165920 940 166453 941 166933 942 167480 943 167987 944 168560 945 169080 946 169560 947 170107 948 170720 949 171173 950 171693 951 172280 952 172827 953 173320 954 173880 955 174400 956 174987 957 175520 958 176013 959 176573 960 177201 961 177667 962 178200 963 178801 964 179361 965 179867 966 180441 967 180974 968 181575 969 182122 970 182628 971 183202 972 183844 973 184322 974 184869 975 185484 976 186058 977 186577 978 187165 979 187712 980 188327 981 188887 982 189406 983 189994 984 190651 985 191142 986 191702 987 192332 988 192920 989 193452 990 194054 991 194614 992 195244 993 195818 994 196350 995 196952 996 197624 997 198128 998 198702 999 199346 1000 199948