0 1 1 1 2 1 3 2 4 2 5 2 6 3 7 3 8 3 9 4 10 4 11 4 12 6 13 5 14 4 15 6 16 6 17 6 18 8 19 7 20 7 21 10 22 9 23 9 24 12 25 10 26 8 27 11 28 11 29 10 30 14 31 13 32 11 33 13 34 12 35 15 36 20 37 17 38 15 39 19 40 19 41 19 42 22 43 18 44 17 45 23 46 22 47 22 48 28 49 25 50 24 51 31 52 28 53 26 54 32 55 32 56 30 57 34 58 32 59 29 60 37 61 33 62 27 63 36 64 33 65 34 66 44 67 38 68 36 69 45 70 45 71 42 72 52 73 45 74 38 75 50 76 45 77 47 78 55 79 52 80 54 81 58 82 58 83 58 84 67 85 66 86 59 87 69 88 66 89 61 90 77 91 76 92 71 93 81 94 78 95 79 96 89 97 83 98 81 99 92 100 93 101 92 102 101 103 94 104 91 105 111 106 104 107 103 108 122 109 108 110 113 111 130 112 121 113 119 114 128 115 126 116 123 117 138 118 129 119 131 120 155 121 142 122 135 123 149 124 136 125 139 126 161 127 147 128 142 129 155 130 153 131 151 132 166 133 160 134 148 135 174 136 170 137 160 138 182 139 171 140 174 141 193 142 181 143 183 144 203 145 195 146 186 147 209 148 199 149 196 150 223 151 207 152 201 153 230 154 224 155 228 156 257 157 234 158 232 159 256 160 246 161 251 162 270 163 257 164 252 165 285 166 272 167 268 168 304 169 284 170 286 171 319 172 300 173 295 174 324 175 327 176 324 177 348 178 336 179 330 180 372 181 358 182 350 183 377 184 362 185 364 186 392 187 379 188 373 189 411 190 409 191 404 192 433 193 417 194 410 195 451 196 448 197 436 198 479 199 473 200 469 201 501 202 487 203 490 204 526 205 529 206 509 207 548 208 549 209 541 210 605 211 587 212 570 213 613 214 604 215 602 216 651 217 642 218 620 219 661 220 662 221 655 222 683 223 676 224 671 225 717 226 708 227 696 228 740 229 722 230 731 231 787 232 763 233 754 234 808 235 801 236 793 237 839 238 830 239 822 240 887 241 864 242 845 243 897 244 873 245 885 246 939 247 924 248 911 249 964 250 957 251 939 252 1014 253 995 254 970 255 1056 256 1036 257 1010 258 1070 259 1062 260 1064 261 1122 262 1111 263 1099 264 1158 265 1153 266 1141 267 1193 268 1168 269 1159 270 1245 271 1211 272 1192 273 1277 274 1245 275 1256 276 1334 277 1291 278 1283 279 1368 280 1364 281 1345 282 1419 283 1382 284 1366 285 1467 286 1433 287 1434 288 1517 289 1480 290 1493 291 1576 292 1530 293 1522 294 1607 295 1586 296 1574 297 1656 298 1622 299 1616 300 1731 301 1697 302 1676 303 1759 304 1730 305 1741 306 1834 307 1798 308 1805 309 1888 310 1862 311 1868 312 1951 313 1898 314 1885 315 2010 316 1962 317 1947 318 2058 319 2020 320 2022 321 2123 322 2086 323 2081 324 2189 325 2174 326 2165 327 2257 328 2217 329 2218 330 2349 331 2288 332 2278 333 2406 334 2346 335 2372 336 2497 337 2421 338 2412 339 2540 340 2514 341 2510 342 2623 343 2585 344 2582 345 2722 346 2676 347 2659 348 2779 349 2713 350 2745 351 2875 352 2807 353 2810 354 2932 355 2900 356 2886 357 3026 358 2972 359 2946 360 3136 361 3076 362 3036 363 3192 364 3134 365 3140 366 3281 367 3220 368 3207 369 3335 370 3302 371 3291 372 3420 373 3363 374 3354 375 3517 376 3449 377 3442 378 3604 379 3521 380 3543 381 3688 382 3602 383 3607 384 3739 385 3707 386 3690 387 3821 388 3777 389 3760 390 3932 391 3873 392 3861 393 4000 394 3928 395 3965 396 4122 397 4041 398 4046 399 4210 400 4169 401 4161 402 4301 403 4251 404 4229 405 4425 406 4388 407 4371 408 4552 409 4484 410 4521 411 4671 412 4590 413 4614 414 4765 415 4740 416 4749 417 4897 418 4857 419 4853 420 5063 421 4990 422 4957 423 5153 424 5085 425 5120 426 5291 427 5232 428 5241 429 5415 430 5392 431 5389 432 5576 433 5514 434 5508 435 5730 436 5649 437 5662 438 5855 439 5774 440 5844 441 6026 442 5972 443 6011 444 6181 445 6151 446 6166 447 6354 448 6304 449 6305 450 6551 451 6494 452 6498 453 6712 454 6632 455 6719 456 6922 457 6850 458 6882 459 7070 460 7073 461 7093 462 7326 463 7272 464 7284 465 7573 466 7496 467 7512 468 7781 469 7724 470 7783 471 8019 472 7962 473 8010 474 8236 475 8251 476 8293 477 8518 478 8492 479 8516 480 8806 481 8745 482 8774 483 9068 484 8993 485 9086 486 9356 487 9288 488 9342 489 9582 490 9600 491 9625 492 9874 493 9860 494 9890 495 10236 496 10201 497 10251 498 10539 499 10474 500 10582 501 10844 502 10796 503 10872 504 11173 505 11177 506 11227 507 11521 508 11483 509 11540 510 11899 511 11865 512 11911 513 12241 514 12182 515 12308 516 12612 517 12565 518 12677 519 12960 520 12994 521 13042 522 13355 523 13331 524 13367 525 13798 526 13719 527 13811 528 14212 529 14115 530 14260 531 14626 532 14586 533 14684 534 15030 535 15042 536 15088 537 15457 538 15449 539 15532 540 15997 541 15932 542 16002 543 16394 544 16323 545 16489 546 16884 547 16819 548 16937 549 17321 550 17341 551 17444 552 17849 553 17854 554 17913 555 18386 556 18343 557 18410 558 18863 559 18823 560 19024 561 19446 562 19391 563 19519 564 19914 565 19941 566 20017 567 20491 568 20465 569 20527 570 21083 571 21008 572 21127 573 21620 574 21578 575 21753 576 22217 577 22157 578 22272 579 22738 580 22754 581 22890 582 23355 583 23331 584 23405 585 23974 586 23921 587 24027 588 24587 589 24493 590 24690 591 25187 592 25116 593 25261 594 25770 595 25846 596 25939 597 26477 598 26465 599 26525 600 27177 601 27086 602 27207 603 27792 604 27707 605 27937 606 28457 607 28404 608 28561 609 29127 610 29147 611 29249 612 29854 613 29790 614 29874 615 30589 616 30547 617 30637 618 31265 619 31174 620 31322 621 31939 622 31870 623 32041 624 32655 625 32659 626 32761 627 33386 628 33326 629 33417 630 34246 631 34100 632 34200 633 34923 634 34752 635 34966 636 35634 637 35573 638 35711 639 36390 640 36373 641 36442 642 37153 643 37045 644 37192 645 37985 646 37835 647 37975 648 38730 649 38572 650 38789 651 39566 652 39407 653 39544 654 40253 655 40207 656 40307 657 41069 658 41007 659 41077 660 41960 661 41795 662 41869 663 42682 664 42496 665 42763 666 43522 667 43368 668 43538 669 44255 670 44213 671 44330 672 45157 673 45007 674 45078 675 46002 676 45807 677 45929 678 46795 679 46627 680 46831 681 47653 682 47498 683 47606 684 48418 685 48340 686 48472 687 49308 688 49133 689 49231 690 50187 691 49977 692 50070 693 51067 694 50818 695 51039 696 51953 697 51687 698 51819 699 52697 700 52648 701 52698 702 53621 703 53475 704 53546 705 54584 706 54325 707 54493 708 55428 709 55151 710 55390 711 56291 712 56038 713 56201 714 57211 715 57048 716 57125 717 58106 718 57845 719 57908 720 59032 721 58772 722 58822 723 59854 724 59549 725 59766 726 60738 727 60422 728 60603 729 61569 730 61401 731 61492 732 62471 733 62197 734 62266 735 63471 736 63100 737 63173 738 64274 739 63897 740 64136 741 65163 742 64871 743 64995 744 66015 745 65811 746 65825 747 66908 748 66622 749 66733 750 67927 751 67509 752 67611 753 68676 754 68293 755 68516 756 69663 757 69227 758 69337 759 70502 760 70189 761 70243 762 71332 763 71021 764 71016 765 72325 766 71926 767 71950 768 73175 769 72729 770 73005 771 74086 772 73648 773 73769 774 74904 775 74640 776 74671 777 75931 778 75483 779 75541 780 76951 781 76445 782 76509 783 77774 784 77384 785 77582 786 78804 787 78329 788 78390 789 79649 790 79324 791 79425 792 80672 793 80206 794 80294 795 81756 796 81193 797 81245 798 82661 799 82124 800 82360 801 83644 802 83089 803 83242 804 84571 805 84287 806 84285 807 85583 808 85135 809 85158 810 86732 811 86170 812 86323 813 87709 814 87150 815 87445 816 88720 817 88191 818 88315 819 89762 820 89404 821 89462 822 90865 823 90355 824 90454 825 92043 826 91537 827 91545 828 93061 829 92584 830 92831 831 94257 832 93683 833 93926 834 95344 835 94974 836 95067 837 96510 838 96041 839 96171 840 97980 841 97286 842 97351 843 99003 844 98374 845 98676 846 100228 847 99741 848 99877 849 101469 850 101126 851 101186 852 102751 853 102212 854 102428 855 104215 856 103609 857 103779 858 105466 859 104888 860 105249 861 106942 862 106299 863 106491 864 108247 865 107854 866 107953 867 109689 868 109221 869 109355 870 111295 871 110688 872 110800 873 112666 874 112128 875 112601 876 114324 877 113724 878 114005 879 115754 880 115455 881 115553 882 117474 883 116969 884 117157 885 119321 886 118650 887 118860 888 120805 889 120342 890 120720 891 122573 892 122073 893 122332 894 124313 895 124053 896 124264 897 126150 898 125721 899 126034 900 128280 901 127740 902 128018 903 130204 904 129666 905 130205 906 132226 907 131645 908 132043 909 134153 910 133982 911 134218 912 136337 913 135929 914 136255 915 138670 916 138100 917 138527 918 140746 919 140296 920 141001 921 143117 922 142642 923 143129 924 145488 925 145255 926 145513 927 147869 928 147514 929 147941 930 150578 931 150139 932 150481 933 152966 934 152629 935 153317 936 155687 937 155285 938 155941 939 158364 940 158228 941 158648 942 161061 943 160790 944 161309 945 164176 946 163744 947 164254 948 166939 949 166617 950 167485 951 169957 952 169725 953 170360 954 172971 955 173071 956 173569 957 176228 958 176026 959 176762 960 179677 961 179327 962 179984 963 182786 964 182645 965 183583 966 186419 967 186139 968 186894 969 189801 970 189852 971 190481 972 193373 973 193388 974 194079 975 197356 976 197162 977 197857 978 200939 979 200853 980 202003 981 204928 982 204824 983 205730 984 208845 985 209034 986 209785 987 212997 988 212973 989 213922 990 217507 991 217331 992 218263 993 221590 994 221670 995 222894 996 226033 997 226077 998 227099 999 230564 1000 230932