0 1 1 0 2 0 3 1 4 1 5 1 6 1 7 1 8 2 9 3 10 2 11 2 12 4 13 4 14 4 15 5 16 5 17 6 18 8 19 7 20 8 21 10 22 10 23 11 24 13 25 13 26 14 27 17 28 17 29 18 30 21 31 21 32 23 33 26 34 26 35 28 36 32 37 32 38 34 39 38 40 39 41 41 42 45 43 46 44 49 45 54 46 54 47 57 48 63 49 64 50 67 51 72 52 74 53 78 54 84 55 85 56 89 57 96 58 98 59 102 60 109 61 111 62 116 63 124 64 126 65 131 66 139 67 142 68 148 69 156 70 159 71 165 72 175 73 178 74 184 75 194 76 198 77 205 78 215 79 219 80 227 81 238 82 242 83 250 84 262 85 267 86 275 87 287 88 293 89 302 90 315 91 320 92 330 93 344 94 350 95 360 96 374 97 381 98 392 99 407 100 414 101 425 102 441 103 449 104 461 105 477 106 485 107 498 108 516 109 524 110 537 111 555 112 565 113 579 114 597 115 607 116 622 117 642 118 652 119 667 120 688 121 699 122 715 123 736 124 748 125 765 126 787 127 799 128 817 129 840 130 853 131 871 132 895 133 909 134 928 135 953 136 967 137 987 138 1013 139 1028 140 1049 141 1075 142 1091 143 1113 144 1141 145 1157 146 1179 147 1208 148 1226 149 1249 150 1278 151 1296 152 1321 153 1352 154 1370 155 1395 156 1427 157 1447 158 1473 159 1505 160 1526 161 1553 162 1587 163 1608 164 1636 165 1671 166 1693 167 1722 168 1758 169 1781 170 1811 171 1848 172 1872 173 1903 174 1941 175 1966 176 1998 177 2037 178 2063 179 2096 180 2137 181 2163 182 2197 183 2239 184 2267 185 2302 186 2344 187 2373 188 2410 189 2454 190 2483 191 2520 192 2566 193 2597 194 2635 195 2681 196 2713 197 2753 198 2801 199 2833 200 2874 201 2923 202 2957 203 2999 204 3049 205 3084 206 3127 207 3179 208 3215 209 3259 210 3312 211 3349 212 3395 213 3449 214 3487 215 3534 216 3590 217 3629 218 3677 219 3734 220 3775 221 3824 222 3882 223 3924 224 3975 225 4035 226 4077 227 4129 228 4191 229 4235 230 4288 231 4350 232 4396 233 4451 234 4515 235 4561 236 4617 237 4683 238 4731 239 4788 240 4855 241 4904 242 4963 243 5032 244 5082 245 5142 246 5212 247 5264 248 5326 249 5397 250 5450 251 5513 252 5587 253 5641 254 5705 255 5780 256 5836 257 5902 258 5978 259 6035 260 6103 261 6181 262 6239 263 6308 264 6388 265 6448 266 6518 267 6599 268 6661 269 6733 270 6816 271 6878 272 6952 273 7037 274 7101 275 7176 276 7262 277 7328 278 7405 279 7493 280 7560 281 7638 282 7728 283 7797 284 7877 285 7968 286 8038 287 8120 288 8214 289 8285 290 8368 291 8463 292 8537 293 8622 294 8718 295 8793 296 8880 297 8979 298 9055 299 9143 300 9244 301 9322 302 9412 303 9514 304 9594 305 9686 306 9790 307 9871 308 9965 309 10071 310 10154 311 10249 312 10357 313 10442 314 10539 315 10649 316 10735 317 10834 318 10946 319 11034 320 11135 321 11248 322 11338 323 11441 324 11557 325 11648 326 11752 327 11870 328 11964 329 12070 330 12189 331 12284 332 12393 333 12515 334 12611 335 12721 336 12845 337 12944 338 13056 339 13181 340 13282 341 13396 342 13524 343 13626 344 13742 345 13872 346 13976 347 14094 348 14226 349 14332 350 14452 351 14586 352 14694 353 14816 354 14952 355 15062 356 15186 357 15324 358 15436 359 15562 360 15703 361 15816 362 15944 363 16087 364 16203 365 16333 366 16477 367 16595 368 16728 369 16875 370 16994 371 17128 372 17278 373 17400 374 17536 375 17687 376 17811 377 17950 378 18104 379 18229 380 18370 381 18526 382 18654 383 18797 384 18955 385 19085 386 19230 387 19391 388 19523 389 19670 390 19833 391 19967 392 20117 393 20282 394 20418 395 20570 396 20738 397 20876 398 21030 399 21200 400 21341 401 21497 402 21669 403 21812 404 21971 405 22146 406 22290 407 22451 408 22629 409 22776 410 22939 411 23118 412 23268 413 23434 414 23616 415 23767 416 23935 417 24120 418 24274 419 24444 420 24631 421 24787 422 24960 423 25150 424 25308 425 25483 426 25675 427 25836 428 26014 429 26208 430 26371 431 26551 432 26749 433 26914 434 27096 435 27296 436 27464 437 27649 438 27851 439 28021 440 28209 441 28414 442 28586 443 28776 444 28984 445 29159 446 29351 447 29561 448 29739 449 29934 450 30147 451 30326 452 30524 453 30740 454 30922 455 31122 456 31340 457 31525 458 31728 459 31949 460 32136 461 32341 462 32565 463 32755 464 32963 465 33189 466 33381 467 33592 468 33822 469 34016 470 34229 471 34461 472 34659 473 34875 474 35109 475 35309 476 35528 477 35766 478 35968 479 36189 480 36430 481 36635 482 36859 483 37102 484 37310 485 37537 486 37783 487 37993 488 38223 489 38472 490 38685 491 38917 492 39169 493 39385 494 39620 495 39875 496 40093 497 40331 498 40589 499 40810 500 41051 501 41311 502 41535 503 41779 504 42043 505 42269 506 42515 507 42782 508 43012 509 43261 510 43530 511 43762 512 44015 513 44288 514 44522 515 44777 516 45053 517 45291 518 45549 519 45827 520 46068 521 46329 522 46611 523 46854 524 47118 525 47403 526 47649 527 47916 528 48204 529 48453 530 48723 531 49014 532 49266 533 49539 534 49833 535 50088 536 50364 537 50661 538 50919 539 51198 540 51499 541 51759 542 52041 543 52345 544 52609 545 52894 546 53200 547 53467 548 53756 549 54066 550 54335 551 54626 552 54940 553 55213 554 55507 555 55823 556 56099 557 56397 558 56717 559 56995 560 57296 561 57619 562 57901 563 58205 564 58531 565 58816 566 59123 567 59453 568 59741 569 60051 570 60384 571 60675 572 60989 573 61325 574 61619 575 61936 576 62276 577 62573 578 62893 579 63236 580 63537 581 63860 582 64206 583 64510 584 64837 585 65187 586 65493 587 65823 588 66177 589 66487 590 66820 591 67176 592 67490 593 67827 594 68187 595 68503 596 68843 597 69207 598 69527 599 69870 600 70237 601 70560 602 70907 603 71278 604 71604 605 71954 606 72328 607 72658 608 73012 609 73389 610 73722 611 74079 612 74461 613 74797 614 75157 615 75542 616 75882 617 76246 618 76634 619 76977 620 77345 621 77737 622 78083 623 78454 624 78850 625 79200 626 79574 627 79973 628 80327 629 80705 630 81108 631 81464 632 81846 633 82253 634 82613 635 82998 636 83408 637 83772 638 84161 639 84575 640 84942 641 85334 642 85752 643 86123 644 86519 645 86940 646 87314 647 87714 648 88140 649 88517 650 88920 651 89349 652 89731 653 90138 654 90570 655 90955 656 91366 657 91803 658 92191 659 92605 660 93046 661 93438 662 93856 663 94300 664 94696 665 95118 666 95566 667 95965 668 96391 669 96843 670 97246 671 97675 672 98131 673 98538 674 98971 675 99431 676 99841 677 100278 678 100742 679 101156 680 101597 681 102064 682 102482 683 102927 684 103399 685 103820 686 104268 687 104744 688 105170 689 105622 690 106101 691 106530 692 106987 693 107471 694 107903 695 108363 696 108851 697 109288 698 109752 699 110243 700 110684 701 111152 702 111648 703 112092 704 112564 705 113064 706 113512 707 113988 708 114492 709 114944 710 115424 711 115932 712 116388 713 116872 714 117384 715 117844 716 118332 717 118848 718 119312 719 119804 720 120325 721 120792 722 121288 723 121813 724 122285 725 122785 726 123313 727 123789 728 124294 729 124827 730 125306 731 125814 732 126352 733 126836 734 127348 735 127889 736 128377 737 128894 738 129440 739 129931 740 130452 741 131002 742 131498 743 132023 744 132577 745 133077 746 133606 747 134165 748 134669 749 135202 750 135765 751 136273 752 136811 753 137378 754 137890 755 138432 756 139004 757 139520 758 140066 759 140642 760 141163 761 141713 762 142293 763 142818 764 143373 765 143958 766 144486 767 145045 768 145635 769 146168 770 146731 771 147324 772 147862 773 148430 774 149028 775 149569 776 150141 777 150744 778 151290 779 151866 780 152473 781 153023 782 153604 783 154216 784 154770 785 155355 786 155971 787 156530 788 157120 789 157740 790 158303 791 158897 792 159523 793 160090 794 160688 795 161318 796 161890 797 162493 798 163127 799 163703 800 164311 801 164950 802 165530 803 166142 804 166786 805 167371 806 167987 807 168635 808 169225 809 169846 810 170499 811 171092 812 171718 813 172376 814 172974 815 173604 816 174266 817 174869 818 175504 819 176171 820 176778 821 177417 822 178089 823 178701 824 179345 825 180021 826 180637 827 181286 828 181968 829 182588 830 183241 831 183927 832 184553 833 185211 834 185901 835 186531 836 187194 837 187890 838 188524 839 189191 840 189892 841 190531 842 191203 843 191908 844 192552 845 193229 846 193939 847 194587 848 195269 849 195984 850 196637 851 197323 852 198043 853 198701 854 199392 855 200117 856 200779 857 201475 858 202205 859 202872 860 203573 861 204307 862 204979 863 205685 864 206425 865 207101 866 207811 867 208556 868 209238 869 209953 870 210702 871 211388 872 212109 873 212864 874 213554 875 214279 876 215039 877 215735 878 216465 879 217229 880 217930 881 218665 882 219435 883 220140 884 220880 885 221655 886 222365 887 223110 888 223890 889 224605 890 225355 891 226140 892 226860 893 227615 894 228405 895 229130 896 229890 897 230685 898 231415 899 232180 900 232981 901 233715 902 234485 903 235291 904 236031 905 236806 906 237616 907 238361 908 239142 909 239958 910 240707 911 241492 912 242314 913 243069 914 243859 915 244685 916 245445 917 246241 918 247073 919 247837 920 248638 921 249475 922 250245 923 251051 924 251893 925 252668 926 253479 927 254327 928 255107 929 255923 930 256776 931 257561 932 258383 933 259241 934 260031 935 260858 936 261722 937 262517 938 263349 939 264218 940 265019 941 265856 942 266730 943 267536 944 268379 945 269259 946 270069 947 270917 948 271803 949 272619 950 273472 951 274362 952 275184 953 276043 954 276939 955 277765 956 278629 957 279531 958 280363 959 281232 960 282139 961 282976 962 283851 963 284764 964 285606 965 286486 966 287404 967 288252 968 289138 969 290061 970 290914 971 291805 972 292735 973 293593 974 294489 975 295424 976 296288 977 297190 978 298130 979 298999 980 299907 981 300853 982 301727 983 302640 984 303592 985 304472 986 305390 987 306347 988 307233 989 308157 990 309120 991 310010 992 310940 993 311909 994 312805 995 313740 996 314714 997 315616 998 316557 999 317537 1000 318444