0 1 1 0 2 1 3 0 4 1 5 0 6 2 7 1 8 2 9 1 10 2 11 2 12 3 13 3 14 4 15 3 16 4 17 4 18 6 19 5 20 7 21 6 22 8 23 7 24 10 25 9 26 11 27 10 28 13 29 12 30 15 31 14 32 17 33 16 34 19 35 19 36 22 37 21 38 24 39 24 40 27 41 27 42 31 43 30 44 34 45 33 46 38 47 37 48 42 49 41 50 46 51 45 52 50 53 50 54 55 55 55 56 60 57 60 58 65 59 65 60 71 61 71 62 77 63 77 64 83 65 83 66 90 67 90 68 97 69 97 70 104 71 104 72 112 73 112 74 120 75 120 76 128 77 129 78 137 79 138 80 146 81 147 82 155 83 157 84 166 85 167 86 176 87 177 88 187 89 188 90 199 91 200 92 210 93 211 94 222 95 224 96 235 97 237 98 248 99 250 100 261 101 264 102 276 103 278 104 290 105 293 106 305 107 308 108 321 109 324 110 337 111 340 112 354 113 357 114 371 115 374 116 389 117 392 118 407 119 411 120 426 121 430 122 445 123 450 124 465 125 470 126 486 127 491 128 507 129 512 130 529 131 534 132 552 133 557 134 575 135 580 136 598 137 604 138 623 139 629 140 648 141 654 142 673 143 680 144 700 145 707 146 727 147 734 148 754 149 762 150 783 151 791 152 812 153 820 154 842 155 850 156 873 157 881 158 904 159 912 160 936 161 945 162 969 163 978 164 1002 165 1012 166 1036 167 1047 168 1072 169 1082 170 1107 171 1118 172 1144 173 1155 174 1182 175 1193 176 1220 177 1231 178 1259 179 1271 180 1299 181 1311 182 1340 183 1352 184 1381 185 1394 186 1424 187 1437 188 1467 189 1481 190 1511 191 1525 192 1556 193 1571 194 1602 195 1617 196 1649 197 1664 198 1697 199 1712 200 1746 201 1761 202 1795 203 1811 204 1846 205 1862 206 1897 207 1914 208 1949 209 1967 210 2003 211 2021 212 2057 213 2075 214 2112 215 2131 216 2169 217 2188 218 2226 219 2245 220 2284 221 2304 222 2344 223 2364 224 2404 225 2424 226 2465 227 2486 228 2528 229 2549 230 2591 231 2613 232 2655 233 2678 234 2721 235 2744 236 2787 237 2811 238 2855 239 2879 240 2924 241 2948 242 2994 243 3018 244 3065 245 3090 246 3137 247 3162 248 3210 249 3236 250 3284 251 3311 252 3360 253 3387 254 3436 255 3464 256 3514 257 3542 258 3593 259 3622 260 3673 261 3702 262 3754 263 3784 264 3837 265 3867 266 3921 267 3951 268 4005 269 4036 270 4092 271 4123 272 4179 273 4211 274 4267 275 4300 276 4357 277 4391 278 4448 279 4482 280 4540 281 4575 282 4634 283 4669 284 4729 285 4764 286 4825 287 4861 288 4923 289 4959 290 5021 291 5058 292 5121 293 5159 294 5223 295 5261 296 5325 297 5364 298 5429 299 5469 300 5535 301 5575 302 5641 303 5682 304 5749 305 5791 306 5859 307 5901 308 5970 309 6012 310 6082 311 6125 312 6196 313 6239 314 6311 315 6355 316 6427 317 6472 318 6545 319 6591 320 6664 321 6711 322 6785 323 6832 324 6907 325 6955 326 7031 327 7079 328 7156 329 7205 330 7283 331 7332 332 7411 333 7461 334 7540 335 7591 336 7672 337 7723 338 7804 339 7856 340 7938 341 7991 342 8074 343 8128 344 8211 345 8265 346 8349 347 8405 348 8490 349 8546 350 8632 351 8688 352 8775 353 8832 354 8921 355 8978 356 9067 357 9125 358 9215 359 9274 360 9365 361 9425 362 9516 363 9577 364 9669 365 9731 366 9824 367 9886 368 9980 369 10043 370 10138 371 10202 372 10298 373 10362 374 10459 375 10524 376 10622 377 10688 378 10787 379 10853 380 10953 381 11020 382 11121 383 11189 384 11291 385 11360 386 11462 387 11532 388 11635 389 11706 390 11810 391 11882 392 11987 393 12059 394 12165 395 12238 396 12346 397 12419 398 12528 399 12602 400 12711 401 12786 402 12897 403 12973 404 13084 405 13161 406 13273 407 13351 408 13464 409 13543 410 13657 411 13736 412 13851 413 13932 414 14048 415 14129 416 14246 417 14328 418 14446 419 14529 420 14649 421 14732 422 14852 423 14936 424 15058 425 15143 426 15266 427 15352 428 15475 429 15562 430 15686 431 15775 432 15900 433 15989 434 16115 435 16205 436 16332 437 16423 438 16552 439 16643 440 16773 441 16865 442 16996 443 17089 444 17221 445 17315 446 17448 447 17543 448 17677 449 17773 450 17908 451 18005 452 18141 453 18239 454 18376 455 18475 456 18613 457 18713 458 18852 459 18953 460 19093 461 19195 462 19337 463 19439 464 19582 465 19685 466 19829 467 19933 468 20079 469 20184 470 20330 471 20436 472 20583 473 20691 474 20839 475 20948 476 21097 477 21206 478 21356 479 21467 480 21619 481 21730 482 21883 483 21995 484 22149 485 22262 486 22418 487 22532 488 22688 489 22803 490 22961 491 23077 492 23236 493 23353 494 23513 495 23631 496 23792 497 23912 498 24074 499 24194 500 24357 501 24479 502 24643 503 24766 504 24932 505 25055 506 25222 507 25346 508 25515 509 25640 510 25810 511 25936 512 26107 513 26234 514 26406 515 26535 516 26708 517 26838 518 27012 519 27143 520 27318 521 27450 522 27627 523 27760 524 27938 525 28072 526 28251 527 28386 528 28567 529 28703 530 28885 531 29022 532 29205 533 29343 534 29528 535 29667 536 29853 537 29993 538 30180 539 30322 540 30510 541 30653 542 30842 543 30986 544 31176 545 31322 546 31514 547 31660 548 31853 549 32000 550 32195 551 32343 552 32540 553 32689 554 32886 555 33036 556 33235 557 33387 558 33587 559 33740 560 33941 561 34095 562 34297 563 34453 564 34657 565 34813 566 35018 567 35176 568 35382 569 35541 570 35749 571 35909 572 36118 573 36279 574 36490 575 36652 576 36864 577 37027 578 37241 579 37405 580 37620 581 37786 582 38002 583 38169 584 38386 585 38555 586 38773 587 38943 588 39163 589 39334 590 39555 591 39727 592 39950 593 40123 594 40348 595 40522 596 40748 597 40923 598 41150 599 41327 600 41556 601 41734 602 41964 603 42143 604 42374 605 42555 606 42788 607 42970 608 43204 609 43387 610 43622 611 43807 612 44044 613 44230 614 44468 615 44655 616 44895 617 45083 618 45325 619 45514 620 45757 621 45947 622 46192 623 46384 624 46630 625 46823 626 47070 627 47265 628 47513 629 47710 630 47960 631 48157 632 48408 633 48607 634 48860 635 49060 636 49315 637 49516 638 49772 639 49974 640 50232 641 50436 642 50695 643 50900 644 51161 645 51367 646 51629 647 51837 648 52101 649 52310 650 52575 651 52786 652 53052 653 53264 654 53532 655 53746 656 54015 657 54230 658 54501 659 54717 660 54990 661 55207 662 55482 663 55700 664 55976 665 56196 666 56474 667 56695 668 56974 669 57197 670 57477 671 57702 672 57984 673 58210 674 58493 675 58720 676 59005 677 59234 678 59521 679 59751 680 60039 681 60270 682 60560 683 60793 684 61085 685 61319 686 61612 687 61847 688 62142 689 62379 690 62676 691 62914 692 63212 693 63452 694 63751 695 63993 696 64294 697 64537 698 64839 699 65084 700 65388 701 65634 702 65940 703 66187 704 66495 705 66743 706 67053 707 67303 708 67614 709 67865 710 68178 711 68431 712 68745 713 69000 714 69316 715 69572 716 69889 717 70147 718 70466 719 70725 720 71046 721 71307 722 71629 723 71891 724 72215 725 72479 726 72805 727 73070 728 73398 729 73664 730 73993 731 74261 732 74593 733 74862 734 75195 735 75466 736 75800 737 76073 738 76409 739 76684 740 77021 741 77297 742 77636 743 77914 744 78255 745 78534 746 78877 747 79157 748 79502 749 79784 750 80131 751 80414 752 80762 753 81047 754 81397 755 81684 756 82036 757 82324 758 82677 759 82967 760 83322 761 83614 762 83971 763 84264 764 84622 765 84917 766 85277 767 85574 768 85936 769 86234 770 86598 771 86897 772 87263 773 87564 774 87932 775 88234 776 88604 777 88908 778 89279 779 89585 780 89958 781 90266 782 90640 783 90950 784 91326 785 91637 786 92015 787 92328 788 92708 789 93022 790 93404 791 93720 792 94104 793 94421 794 94807 795 95126 796 95513 797 95834 798 96224 799 96546 800 96937 801 97261 802 97654 803 97980 804 98375 805 98703 806 99099 807 99428 808 99826 809 100158 810 100558 811 100891 812 101293 813 101627 814 102031 815 102367 816 102774 817 103111 818 103519 819 103858 820 104268 821 104609 822 105021 823 105364 824 105777 825 106122 826 106537 827 106884 828 107301 829 107649 830 108068 831 108418 832 108839 833 109191 834 109614 835 109967 836 110392 837 110747 838 111174 839 111531 840 111960 841 112318 842 112749 843 113109 844 113542 845 113904 846 114339 847 114703 848 115139 849 115505 850 115943 851 116311 852 116751 853 117121 854 117563 855 117934 856 118378 857 118751 858 119198 859 119572 860 120021 861 120397 862 120847 863 121225 864 121678 865 122058 866 122512 867 122894 868 123350 869 123734 870 124192 871 124578 872 125038 873 125425 874 125887 875 126277 876 126741 877 127132 878 127598 879 127991 880 128459 881 128854 882 129325 883 129721 884 130193 885 130591 886 131066 887 131466 888 131943 889 132345 890 132823 891 133227 892 133707 893 134114 894 134596 895 135004 896 135488 897 135898 898 136384 899 136796 900 137285 901 137698 902 138189 903 138604 904 139097 905 139514 906 140009 907 140428 908 140925 909 141346 910 141845 911 142268 912 142769 913 143194 914 143697 915 144124 916 144629 917 145058 918 145565 919 145996 920 146505 921 146938 922 147449 923 147884 924 148398 925 148834 926 149350 927 149788 928 150306 929 150746 930 151267 931 151709 932 152231 933 152675 934 153199 935 153646 936 154172 937 154621 938 155149 939 155599 940 156129 941 156582 942 157115 943 157569 944 158104 945 158560 946 159097 947 159555 948 160095 949 160555 950 161096 951 161558 952 162102 953 162566 954 163112 955 163578 956 164126 957 164594 958 165144 959 165615 960 166167 961 166639 962 167193 963 167668 964 168224 965 168701 966 169260 967 169738 968 170299 969 170779 970 171343 971 171825 972 172391 973 172875 974 173443 975 173929 976 174499 977 174988 978 175560 979 176051 980 176625 981 177118 982 177694 983 178189 984 178768 985 179265 986 179846 987 180345 988 180928 989 181429 990 182015 991 182518 992 183106 993 183611 994 184201 995 184708 996 185301 997 185810 998 186405 999 186916 1000 187513