1 0 2 0 3 0 4 1 5 1 6 4 7 4 8 7 9 9 10 14 11 14 12 21 13 21 14 28 15 34 16 41 17 41 18 52 19 52 20 63 21 71 22 82 23 82 24 97 25 101 26 114 27 122 28 137 29 137 30 158 31 158 32 173 33 185 34 202 35 212 36 235 37 235 38 254 39 268 40 291 41 291 42 320 43 320 44 343 45 363 46 386 47 386 48 417 49 423 50 452 51 470 52 497 53 497 54 532 55 546 56 577 57 597 58 626 59 626 60 669 61 669 62 700 63 726 64 757 65 773 66 818 67 818 68 853 69 877 70 922 71 922 72 969 73 969 74 1006 75 1040 76 1079 77 1095 78 1148 79 1148 80 1195 81 1221 82 1262 83 1262 84 1321 85 1341 86 1384 87 1414 88 1461 89 1461 90 1526 91 1544 92 1591 93 1623 94 1670 95 1692 96 1755 97 1755 98 1810 99 1848 100 1907 101 1907 102 1976 103 1976 104 2031 105 2087 106 2140 107 2140 108 2211 109 2211 110 2280 111 2318 112 2381 113 2381 114 2458 115 2484 116 2543 117 2587 118 2646 119 2668 120 2755 121 2765 122 2826 123 2868 124 2931 125 2955 126 3044 127 3044 128 3107 129 3151 130 3232 131 3232 132 3323 133 3347 134 3414 135 3476 136 3547 137 3547 138 3640 139 3640 140 3731 141 3779 142 3850 143 3872 144 3967 145 3999 146 4072 147 4134 148 4209 149 4209 150 4318 151 4318 152 4397 153 4453 154 4546 155 4580 156 4687 157 4687 158 4766 159 4820 160 4915 161 4943 162 5050 163 5050 164 5133 165 5217 166 5300 167 5300 168 5419 169 5431 170 5536 171 5598 172 5685 173 5685 174 5802 175 5856 176 5951 177 6011 178 6100 179 6100 180 6231 181 6231 182 6340 183 6402 184 6497 185 6537 186 6662 187 6688 188 6783 189 6863 190 6980 191 6980 192 7107 193 7107 194 7204 195 7302 196 7413 197 7413 198 7550 199 7550 200 7669 201 7737 202 7838 203 7872 204 8011 205 8055 206 8158 207 8232 208 8343 209 8371 210 8532 211 8532 212 8639 213 8711 214 8818 215 8864 216 9007 217 9043 218 9152 219 9226 220 9365 221 9393 222 9542 223 9542 224 9669 225 9773 226 9886 227 9886 228 10041 229 10041 230 10182 231 10292 232 10411 233 10411 234 10572 235 10622 236 10741 237 10821 238 10962 239 10962 240 11137 241 11137 242 11268 243 11348 244 11471 245 11547 246 11712 247 11742 248 11869 249 11953 250 12102 251 12102 252 12281 253 12313 254 12440 255 12566 256 12693 257 12693 258 12866 259 12908 260 13071 261 13163 262 13294 263 13294 264 13477 265 13533 266 13690 267 13780 268 13915 269 13915 270 14112 271 14112 272 14255 273 14383 274 14520 275 14594 276 14781 277 14781 278 14920 279 15018 280 15201 281 15201 282 15390 283 15390 284 15533 285 15673 286 15838 287 15884 288 16075 289 16091 290 16268 291 16366 292 16513 293 16513 294 16722 295 16784 296 16935 297 17051 298 17200 299 17234 300 17453 301 17501 302 17652 303 17754 304 17913 305 17977 306 18186 307 18186 308 18373 309 18477 310 18666 311 18666 312 18881 313 18881 314 19038 315 19208 316 19367 317 19367 318 19580 319 19618 320 19809 321 19917 322 20106 323 20140 324 20355 325 20439 326 20602 327 20712 328 20879 329 20931 330 21180 331 21180 332 21347 333 21463 334 21630 335 21700 336 21939 337 21939 338 22120 339 22234 340 22445 341 22485 342 22718 343 22766 344 22941 345 23109 346 23282 347 23282 348 23517 349 23517 350 23746 351 23880 352 24071 353 24071 354 24308 355 24382 356 24561 357 24725 358 24904 359 24904 360 25167 361 25185 362 25366 363 25508 364 25727 365 25803 366 26048 367 26048 368 26239 369 26367 370 26592 371 26650 372 26901 373 26901 374 27114 375 27288 376 27479 377 27519 378 27788 379 27788 380 28023 381 28151 382 28342 383 28342 384 28597 385 28741 386 28934 387 29068 388 29263 389 29263 390 29556 391 29594 392 29817 393 29949 394 30146 395 30228 396 30503 397 30503 398 30702 399 30884 400 31123 401 31123 402 31392 403 31434 404 31637 405 31825 406 32062 407 32108 408 32387 409 32387 410 32636 411 32774 412 32981 413 33045 414 33326 415 33412 416 33635 417 33775 418 34012 419 34012 420 34335 421 34335 422 34546 423 34692 424 34907 425 35011 426 35296 427 35362 428 35577 429 35765 430 36026 431 36026 432 36313 433 36313 434 36566 435 36776 436 36995 437 37035 438 37328 439 37328 440 37607 441 37795 442 38044 443 38044 444 38343 445 38435 446 38658 447 38808 448 39063 449 39063 450 39392 451 39442 452 39669 453 39821 454 40048 455 40214 456 40525 457 40525 458 40754 459 40924 460 41207 461 41207 462 41548 463 41548 464 41787 465 42011 466 42244 467 42244 468 42567 469 42639 470 42924 471 43082 472 43321 473 43373 474 43690 475 43804 476 44087 477 44251 478 44490 479 44490 480 44841 481 44889 482 45130 483 45348 484 45611 485 45711 486 46034 487 46034 488 46281 489 46445 490 46766 491 46766 492 47097 493 47141 494 47418 495 47672 496 47927 497 48003 498 48336 499 48336 500 48635 501 48803 502 49054 503 49054 504 49413 505 49517 506 49802 507 49996 508 50251 509 50251 510 50632 511 50710 512 50965 513 51153 514 51410 515 51516 516 51863 517 51919 518 52220 519 52394 520 52721 521 52721 522 53074 523 53074 524 53337 525 53621 526 53884 527 53930 528 54297 529 54319 530 54640 531 54822 532 55137 533 55189 534 55546 535 55656 536 55927 537 56107 538 56376 539 56494 540 56889 541 56889 542 57160 543 57342 544 57629 545 57741 546 58142 547 58142 548 58417 549 58605 550 58954 551 59000 552 59375 553 59459 554 59736 555 60002 556 60281 557 60281 558 60658 559 60712 560 61079 561 61319 562 61600 563 61600 564 61979 565 62095 566 62378 567 62620 568 62907 569 62907 570 63332 571 63332 572 63663 573 63855 574 64188 575 64322 576 64705 577 64705 578 65010 579 65204 580 65559 581 65647 582 66036 583 66098 584 66393 585 66689 586 66982 587 66982 588 67401 589 67449 590 67806 591 68004 592 68307 593 68307 594 68720 595 68930 596 69229 597 69429 598 69762 599 69762 600 70201 601 70201 602 70550 603 70756 604 71059 605 71223 606 71628 607 71628 608 71947 609 72219 610 72588 611 72646 612 73065 613 73065 614 73372 615 73666 616 74041 617 74041 618 74454 619 74454 620 74833 621 75057 622 75368 623 75462 624 75893 625 76017 626 76330 627 76596 628 76911 629 76963 630 77448 631 77448 632 77767 633 77979 634 78296 635 78426 636 78853 637 78985 638 79342 639 79560 640 79943 641 79943 642 80372 643 80372 644 80751 645 81059 646 81416 647 81416 648 81847 649 81915 650 82324 651 82614 652 82941 653 82941 654 83378 655 83512 656 83847 657 84071 658 84452 659 84452 660 84951 661 84951 662 85282 663 85560 664 85895 665 86127 666 86576 667 86626 668 86961 669 87185 670 87590 671 87660 672 88139 673 88139 674 88476 675 88790 676 89153 677 89153 678 89606 679 89708 680 90131 681 90359 682 90740 683 90740 684 91207 685 91347 686 91738 687 91968 688 92319 689 92383 690 92896 691 92896 692 93243 693 93575 694 93922 695 94064 696 94535 697 94591 698 94940 699 95174 700 95633 701 95633 702 96118 703 96172 704 96555 705 96891 706 97244 707 97350 708 97825 709 97825 710 98254 711 98496 712 98855 713 98907 714 99428 715 99662 716 100021 717 100261 718 100620 719 100620 720 101147 721 101255 722 101634 723 101876 724 102239 725 102403 726 102908 727 102908 728 103347 729 103589 730 104030 731 104088 732 104579 733 104579 734 104946 735 105344 736 105727 737 105803 738 106300 739 106300 740 106751 741 107059 742 107488 743 107488 744 107991 745 108143 746 108516 747 108770 748 109197 749 109309 750 109858 751 109858 752 110241 753 110493 754 110910 755 111064 756 111603 757 111603 758 111982 759 112300 760 112771 761 112771 762 113280 763 113394 764 113777 765 114157 766 114540 767 114610 768 115121 769 115121 770 115650 771 115908 772 116295 773 116295 774 116816 775 116990 776 117381 777 117725 778 118114 779 118172 780 118759 781 118839 782 119268 783 119546 784 119993 785 120153 786 120678 787 120678 788 121073 789 121337 790 121814 791 121932 792 122483 793 122555 794 122952 795 123330 796 123729 797 123729 798 124310 799 124372 800 124851 801 125123 802 125524 803 125606 804 126145 805 126421 806 126866 807 127136 808 127543 809 127543 810 128136 811 128136 812 128611 813 128883 814 129336 815 129502 816 130061 817 130121 818 130530 819 130916 820 131415 821 131415 822 131964 823 131964 824 132379 825 132803 826 133280 827 133280 828 133843 829 133843 830 134344 831 134622 832 135069 833 135229 834 135786 835 135956 836 136431 837 136727 838 137146 839 137146 840 137793 841 137821 842 138242 843 138524 844 138947 845 139167 846 139736 847 139922 848 140353 849 140637 850 141166 851 141224 852 141795 853 141795 854 142288 855 142710 856 143141 857 143141 858 143758 859 143758 860 144281 861 144661 862 145092 863 145092 864 145667 865 145843 866 146276 867 146598 868 147105 869 147193 870 147838 871 147916 872 148355 873 148651 874 149128 875 149402 876 149989 877 149989 878 150428 879 150722 880 151281 881 151281 882 151910 883 151910 884 152409 885 152829 886 153272 887 153272 888 153871 889 154003 890 154540 891 154890 892 155337 893 155401 894 155998 895 156180 896 156691 897 157059 898 157508 899 157566 900 158225 901 158293 902 158794 903 159192 904 159647 905 159831 906 160436 907 160436 908 160891 909 161199 910 161820 911 161820 912 162443 913 162535 914 162992 915 163426 916 163885 917 164021 918 164650 919 164650 920 165217 921 165525 922 165986 923 166068 924 166751 925 166955 926 167418 927 167732 928 168211 929 168211 930 168900 931 169074 932 169541 933 169853 934 170320 935 170614 936 171261 937 171261 938 171802 939 172116 940 172687 941 172687 942 173316 943 173378 944 173857 945 174369 946 174894 947 174894 948 175529 949 175613 950 176202 951 176520 952 177087 953 177087 954 177728 955 177922 956 178401 957 178797 958 179276 959 179418 960 180121 961 180151 962 180680 963 181006 964 181489 965 181685 966 182386 967 182386 968 182913 969 183305 970 183890 971 183890 972 184537 973 184681 974 185168 975 185662 976 186157 977 186157 978 186810 979 186908 980 187551 981 187883 982 188374 983 188374 984 189037 985 189237 986 189774 987 190208 988 190763 989 190827 990 191576 991 191576 992 192087 993 192419 994 192992 995 193194 996 193861 997 193861 998 194360 999 194710 1000 195309