0 1 1 0 2 0 3 1 4 1 5 0 6 1 7 2 8 2 9 1 10 2 11 3 12 3 13 2 14 4 15 5 16 5 17 4 18 6 19 7 20 7 21 7 22 9 23 10 24 11 25 10 26 12 27 14 28 15 29 14 30 17 31 19 32 20 33 19 34 22 35 25 36 26 37 25 38 29 39 32 40 33 41 32 42 37 43 40 44 41 45 41 46 46 47 49 48 51 49 51 50 56 51 60 52 62 53 62 54 68 55 72 56 75 57 75 58 81 59 86 60 89 61 89 62 96 63 102 64 105 65 105 66 113 67 119 68 122 69 123 70 132 71 138 72 142 73 143 74 152 75 159 76 163 77 165 78 175 79 182 80 187 81 189 82 199 83 207 84 213 85 215 86 226 87 235 88 241 89 243 90 255 91 265 92 271 93 274 94 287 95 297 96 304 97 307 98 321 99 332 100 339 101 343 102 358 103 369 104 377 105 382 106 397 107 409 108 418 109 423 110 439 111 452 112 462 113 467 114 484 115 498 116 508 117 514 118 532 119 547 120 558 121 564 122 583 123 599 124 610 125 617 126 638 127 654 128 666 129 674 130 695 131 712 132 725 133 734 134 756 135 774 136 788 137 797 138 820 139 839 140 854 141 864 142 888 143 908 144 924 145 934 146 959 147 981 148 997 149 1008 150 1035 151 1057 152 1074 153 1086 154 1114 155 1137 156 1155 157 1168 158 1197 159 1221 160 1240 161 1254 162 1284 163 1309 164 1329 165 1344 166 1375 167 1401 168 1423 169 1438 170 1470 171 1498 172 1520 173 1536 174 1570 175 1599 176 1622 177 1639 178 1674 179 1704 180 1728 181 1746 182 1783 183 1814 184 1839 185 1858 186 1896 187 1928 188 1954 189 1975 190 2014 191 2047 192 2075 193 2096 194 2136 195 2171 196 2200 197 2222 198 2264 199 2300 200 2330 201 2353 202 2396 203 2434 204 2465 205 2489 206 2534 207 2573 208 2605 209 2630 210 2677 211 2717 212 2750 213 2777 214 2825 215 2866 216 2901 217 2929 218 2978 219 3021 220 3057 221 3086 222 3137 223 3181 224 3219 225 3249 226 3301 227 3347 228 3386 229 3417 230 3471 231 3519 232 3559 233 3591 234 3647 235 3696 236 3737 237 3771 238 3829 239 3879 240 3922 241 3957 242 4016 243 4068 244 4112 245 4149 246 4210 247 4263 248 4309 249 4347 250 4409 251 4464 252 4512 253 4551 254 4615 255 4672 256 4721 257 4761 258 4827 259 4886 260 4936 261 4978 262 5046 263 5106 264 5158 265 5201 266 5271 267 5333 268 5386 269 5431 270 5503 271 5566 272 5621 273 5668 274 5741 275 5806 276 5863 277 5911 278 5986 279 6053 280 6112 281 6161 282 6238 283 6307 284 6367 285 6418 286 6497 287 6568 288 6630 289 6682 290 6763 291 6836 292 6899 293 6953 294 7037 295 7111 296 7176 297 7232 298 7317 299 7393 300 7460 301 7518 302 7605 303 7683 304 7752 305 7811 306 7900 307 7980 308 8051 309 8112 310 8203 311 8285 312 8358 313 8420 314 8513 315 8598 316 8672 317 8736 318 8832 319 8918 320 8994 321 9060 322 9158 323 9246 324 9324 325 9392 326 9492 327 9582 328 9662 329 9732 330 9834 331 9926 332 10008 333 10080 334 10184 335 10278 336 10363 337 10436 338 10542 339 10639 340 10725 341 10800 342 10909 343 11008 344 11096 345 11173 346 11284 347 11385 348 11475 349 11554 350 11668 351 11771 352 11863 353 11944 354 12060 355 12165 356 12259 357 12343 358 12461 359 12568 360 12665 361 12750 362 12870 363 12980 364 13079 365 13166 366 13289 367 13401 368 13502 369 13591 370 13716 371 13831 372 13934 373 14025 374 14153 375 14270 376 14375 377 14468 378 14599 379 14718 380 14825 381 14921 382 15054 383 15175 384 15285 385 15383 386 15518 387 15642 388 15754 389 15854 390 15992 391 16118 392 16233 393 16335 394 16475 395 16604 396 16721 397 16825 398 16968 399 17100 400 17219 401 17325 402 17471 403 17605 404 17726 405 17835 406 17984 407 18120 408 18244 409 18355 410 18506 411 18645 412 18771 413 18885 414 19039 415 19180 416 19309 417 19425 418 19581 419 19725 420 19857 421 19975 422 20134 423 20281 424 20415 425 20535 426 20697 427 20847 428 20983 429 21106 430 21271 431 21423 432 21562 433 21687 434 21855 435 22010 436 22151 437 22279 438 22450 439 22607 440 22751 441 22882 442 23055 443 23215 444 23362 445 23495 446 23671 447 23834 448 23984 449 24119 450 24298 451 24464 452 24616 453 24754 454 24936 455 25105 456 25260 457 25400 458 25585 459 25757 460 25914 461 26057 462 26246 463 26420 464 26580 465 26726 466 26917 467 27094 468 27257 469 27406 470 27600 471 27780 472 27946 473 28097 474 28294 475 28477 476 28646 477 28800 478 29000 479 29186 480 29358 481 29514 482 29717 483 29907 484 30081 485 30240 486 30447 487 30639 488 30816 489 30978 490 31188 491 31383 492 31563 493 31728 494 31941 495 32139 496 32322 497 32490 498 32706 499 32907 500 33093 501 33264 502 33483 503 33687 504 33877 505 34050 506 34272 507 34480 508 34672 509 34848 510 35074 511 35285 512 35480 513 35659 514 35888 515 36102 516 36300 517 36482 518 36715 519 36932 520 37133 521 37318 522 37554 523 37774 524 37978 525 38167 526 38406 527 38629 528 38837 529 39028 530 39270 531 39497 532 39708 533 39902 534 40148 535 40378 536 40592 537 40789 538 41038 539 41272 540 41489 541 41689 542 41942 543 42179 544 42399 545 42602 546 42859 547 43099 548 43322 549 43529 550 43789 551 44032 552 44259 553 44469 554 44732 555 44979 556 45209 557 45422 558 45689 559 45939 560 46173 561 46389 562 46659 563 46913 564 47150 565 47369 566 47643 567 47901 568 48141 569 48363 570 48641 571 48902 572 49145 573 49371 574 49653 575 49917 576 50164 577 50393 578 50678 579 50946 580 51196 581 51429 582 51718 583 51989 584 52243 585 52479 586 52771 587 53046 588 53304 589 53543 590 53839 591 54118 592 54379 593 54621 594 54921 595 55204 596 55468 597 55714 598 56018 599 56304 600 56572 601 56821 602 57129 603 57419 604 57690 605 57943 606 58255 607 58548 608 58823 609 59080 610 59395 611 59692 612 59971 613 60231 614 60550 615 60851 616 61134 617 61397 618 61720 619 62025 620 62311 621 62578 622 62905 623 63214 624 63504 625 63774 626 64105 627 64418 628 64711 629 64985 630 65321 631 65637 632 65934 633 66212 634 66551 635 66871 636 67172 637 67454 638 67797 639 68121 640 68426 641 68711 642 69058 643 69386 644 69695 645 69984 646 70335 647 70667 648 70980 649 71272 650 71627 651 71964 652 72280 653 72576 654 72936 655 73276 656 73596 657 73896 658 74260 659 74604 660 74928 661 75232 662 75600 663 75948 664 76276 665 76584 666 76956 667 77308 668 77640 669 77952 670 78328 671 78684 672 79021 673 79336 674 79716 675 80077 676 80417 677 80736 678 81121 679 81486 680 81830 681 82153 682 82542 683 82911 684 83259 685 83586 686 83980 687 84353 688 84705 689 85036 690 85434 691 85811 692 86167 693 86503 694 86905 695 87286 696 87647 697 87986 698 88392 699 88778 700 89143 701 89486 702 89897 703 90287 704 90656 705 91003 706 91418 707 91813 708 92186 709 92537 710 92957 711 93356 712 93733 713 94088 714 94513 715 94916 716 95297 717 95657 718 96086 719 96493 720 96879 721 97243 722 97676 723 98088 724 98478 725 98846 726 99284 727 99700 728 100095 729 100467 730 100909 731 101330 732 101729 733 102105 734 102552 735 102978 736 103381 737 103761 738 104213 739 104643 740 105050 741 105435 742 105892 743 106326 744 106738 745 107127 746 107588 747 108027 748 108443 749 108837 750 109303 751 109746 752 110167 753 110565 754 111035 755 111483 756 111909 757 112311 758 112786 759 113239 760 113669 761 114075 762 114555 763 115013 764 115447 765 115858 766 116343 767 116805 768 117244 769 117659 770 118149 771 118616 772 119059 773 119479 774 119974 775 120445 776 120893 777 121318 778 121817 779 122293 780 122746 781 123175 782 123679 783 124160 784 124618 785 125051 786 125560 787 126046 788 126508 789 126946 790 127460 791 127951 792 128418 793 128860 794 129379 795 129875 796 130346 797 130793 798 131318 799 131818 800 132294 801 132746 802 133275 803 133780 804 134261 805 134718 806 135252 807 135762 808 136248 809 136709 810 137248 811 137763 812 138254 813 138720 814 139264 815 139784 816 140280 817 140750 818 141299 819 141825 820 142325 821 142800 822 143355 823 143885 824 144390 825 144870 826 145430 827 145965 828 146475 829 146960 830 147525 831 148065 832 148580 833 149070 834 149640 835 150185 836 150705 837 151200 838 151775 839 152325 840 152851 841 153350 842 153930 843 154486 844 155016 845 155520 846 156106 847 156667 848 157202 849 157711 850 158302 851 158868 852 159408 853 159922 854 160519 855 161090 856 161635 857 162154 858 162756 859 163332 860 163882 861 164407 862 165014 863 165595 864 166151 865 166680 866 167292 867 167879 868 168440 869 168974 870 169592 871 170184 872 170750 873 171289 874 171912 875 172510 876 173081 877 173625 878 174254 879 174857 880 175433 881 175982 882 176617 883 177225 884 177806 885 178361 886 179001 887 179614 888 180201 889 180761 890 181406 891 182025 892 182617 893 183182 894 183833 895 184457 896 185055 897 185625 898 186281 899 186911 900 187514 901 188089 902 188751 903 189387 904 189995 905 190575 906 191243 907 191884 908 192497 909 193083 910 193757 911 194403 912 195022 913 195613 914 196292 915 196944 916 197568 917 198165 918 198850 919 199507 920 200137 921 200739 922 201429 923 202092 924 202728 925 203335 926 204031 927 204700 928 205341 929 205953 930 206655 931 207330 932 207976 933 208594 934 209302 935 209982 936 210634 937 211257 938 211971 939 212657 940 213314 941 213943 942 214663 943 215354 944 216017 945 216652 946 217377 947 218074 948 218743 949 219383 950 220114 951 220817 952 221492 953 222137 954 222874 955 223583 956 224263 957 224914 958 225657 959 226372 960 227058 961 227714 962 228463 963 229184 964 229875 965 230537 966 231293 967 232019 968 232716 969 233384 970 234145 971 234877 972 235580 973 236254 974 237021 975 237759 976 238468 977 239147 978 239920 979 240664 980 241379 981 242064 982 242843 983 243593 984 244314 985 245004 986 245789 987 246546 988 247272 989 247968 990 248760 991 249522 992 250254 993 250956 994 251754 995 252522 996 253260 997 253968 998 254772 999 255546 1000 256290