0 1 1 0 2 2 3 2 4 3 5 2 6 5 7 2 8 5 9 4 10 5 11 2 12 8 13 2 14 9 15 8 16 9 17 2 18 9 19 2 20 11 21 8 22 9 23 2 24 15 25 6 26 9 27 10 28 15 29 2 30 20 31 2 32 17 33 8 34 5 35 10 36 15 37 2 38 9 39 10 40 19 41 2 42 23 43 2 44 19 45 20 46 17 47 2 48 29 49 8 50 17 51 20 52 19 53 2 54 29 55 10 56 24 57 8 58 17 59 2 60 35 61 2 62 33 63 18 64 33 65 16 66 19 67 2 68 11 69 20 70 27 71 2 72 33 73 2 74 9 75 30 76 19 77 16 78 41 79 2 80 31 81 28 82 9 83 2 84 32 85 16 86 17 87 8 88 33 89 2 90 38 91 20 92 35 93 10 94 33 95 24 96 47 97 2 98 21 99 28 100 33 101 2 102 29 103 2 104 35 105 30 106 17 107 2 108 49 109 2 110 49 111 10 112 47 113 2 114 31 115 24 116 35 117 28 118 33 119 18 120 69 121 12 122 33 123 26 124 51 125 26 126 85 127 2 128 65 129 26 130 15 131 2 132 44 133 24 134 9 135 44 136 23 137 2 138 23 139 2 140 39 141 20 142 17 143 16 144 53 145 14 146 9 147 42 148 23 149 2 150 57 151 2 152 43 153 50 154 28 155 12 156 67 157 2 158 33 159 56 160 55 161 18 162 61 163 2 164 23 165 28 166 17 167 2 168 53 169 14 170 37 171 28 172 43 173 2 174 45 175 42 176 61 177 20 178 17 179 2 180 71 181 2 182 56 183 20 184 63 185 22 186 57 187 24 188 67 189 60 190 83 191 2 192 87 193 2 194 9 195 48 196 43 197 2 198 53 199 2 200 63 201 26 202 17 203 16 204 71 205 20 206 33 207 56 208 59 209 28 210 79 211 2 212 43 213 56 214 33 215 36 216 101 217 26 218 33 219 20 220 100 221 22 222 85 223 2 224 99 225 74 226 17 227 2 228 69 229 2 230 57 231 92 232 63 233 2 234 93 235 34 236 67 237 56 238 95 239 2 240 155 241 2 242 51 243 82 244 67 245 78 246 69 247 26 248 95 249 8 250 101 251 2 252 110 253 16 254 129 255 26 256 129 257 2 258 19 259 24 260 29 261 28 262 9 263 2 264 33 265 16 266 43 267 20 268 19 269 2 270 49 271 2 272 51 273 52 274 9 275 34 276 41 277 2 278 17 279 34 280 80 281 2 282 35 283 2 284 35 285 52 286 59 287 48 288 87 289 18 290 39 291 26 292 23 293 2 294 83 295 34 296 49 297 66 298 17 299 34 300 75 301 20 302 33 303 20 304 77 305 22 306 54 307 2 308 73 309 26 310 63 311 2 312 114 313 2 314 33 315 110 316 67 317 2 318 91 319 34 320 125 321 56 322 53 323 22 324 87 325 70 326 17 327 10 328 49 329 48 330 69 331 2 332 43 333 34 334 33 335 40 336 113 337 2 338 41 339 26 340 98 341 40 342 83 343 50 344 77 345 94 346 33 347 2 348 113 349 2 350 115 351 60 352 125 353 2 354 35 355 34 356 43 357 36 358 33 359 2 360 143 361 20 362 33 363 64 364 93 365 64 366 103 367 2 368 119 369 74 370 109 371 16 372 123 373 2 374 76 375 134 376 119 377 24 378 139 379 2 380 136 381 26 382 129 383 2 384 181 385 34 386 9 387 70 388 19 389 2 390 83 391 30 392 55 393 74 394 17 395 24 396 127 397 2 398 33 399 82 400 89 401 2 402 123 403 30 404 43 405 128 406 55 407 30 408 96 409 2 410 59 411 20 412 67 413 22 414 113 415 36 416 121 417 26 418 44 419 2 420 116 421 2 422 33 423 74 424 79 425 66 426 69 427 30 428 83 429 100 430 91 431 2 432 169 433 2 434 71 435 70 436 83 437 28 438 97 439 2 440 170 441 90 442 101 443 2 444 169 445 64 446 129 447 74 448 177 449 2 450 157 451 46 452 35 453 74 454 33 455 76 456 170 457 2 458 33 459 136 460 119 461 2 462 142 463 2 464 123 465 120 466 33 467 2 468 171 469 36 470 139 471 74 472 127 473 54 474 163 475 94 476 172 477 134 478 129 479 2 480 263 481 48 482 33 483 204 484 103 485 64 486 205 487 2 488 119 489 8 490 167 491 2 492 143 493 42 494 167 495 124 496 187 497 22 498 79 499 2 500 203 501 20 502 129 503 2 504 211 505 14 506 155 507 56 508 195 509 2 510 289 511 38 512 257 513 68 514 5 515 24 516 29 517 30 518 59 519 20 520 45 521 2 522 65 523 2 524 19 525 106 526 17 527 46 528 87 529 24 530 35 531 74 532 90 533 24 534 53 535 34 536 43 537 56 538 17 539 86 540 133 541 2 542 33 543 20 544 93 545 54 546 65 547 2 548 23 549 74 550 107 551 40 552 76 553 36 554 17 555 92 556 43 557 2 558 137 559 32 560 149 561 116 562 17 563 2 564 119 565 64 566 33 567 160 568 79 569 2 570 129 571 2 572 121 573 20 574 129 575 88 576 145 577 2 578 41 579 26 580 77 581 76 582 53 583 60 584 57 585 146 586 17 587 2 588 137 589 44 590 117 591 56 592 91 593 2 594 145 595 126 596 51 597 26 598 68 599 2 600 201 601 2 602 79 603 76 604 83 605 100 606 107 607 2 608 147 609 132 610 97 611 48 612 139 613 2 614 33 615 174 616 146 617 2 618 139 619 2 620 205 621 142 622 65 623 78 624 188 625 126 626 33 627 94 628 83 629 28 630 212 631 2 632 151 633 74 634 65 635 10 636 215 637 122 638 165 639 152 640 197 641 2 642 119 643 2 644 56 645 178 646 59 647 2 648 211 649 40 650 76 651 78 652 43 653 2 654 59 655 12 656 93 657 68 658 83 659 2 660 118 661 2 662 33 663 120 664 95 665 114 666 141 667 36 668 83 669 56 670 83 671 52 672 251 673 2 674 17 675 150 676 95 677 2 678 69 679 104 680 113 681 56 682 99 683 2 684 203 685 22 686 153 687 74 688 155 689 22 690 166 691 2 692 99 693 190 694 65 695 34 696 245 697 40 698 65 699 164 700 201 701 2 702 283 703 56 704 251 705 80 706 17 707 18 708 125 709 2 710 63 711 134 712 95 713 40 714 165 715 112 716 83 717 164 718 65 719 2 720 311 721 24 722 69 723 164 724 99 725 86 726 327 727 2 728 189 729 244 730 87 731 46 732 173 733 2 734 129 735 64 736 225 737 24 738 59 739 2 740 131 741 40 742 87 743 2 744 175 745 54 746 65 747 28 748 197 749 24 750 193 751 2 752 231 753 20 754 119 755 12 756 208 757 2 758 129 759 54 760 237 761 2 762 143 763 36 764 259 765 74 766 257 767 52 768 329 769 2 770 93 771 26 772 19 773 2 774 67 775 60 776 43 777 82 778 17 779 30 780 115 781 52 782 91 783 94 784 129 785 28 786 31 787 2 788 43 789 20 790 71 791 24 792 147 793 62 794 33 795 74 796 67 797 2 798 123 799 58 800 169 801 68 802 17 803 66 804 83 805 82 806 107 807 56 808 95 809 2 810 143 811 2 812 145 813 10 814 139 815 52 816 191 817 36 818 33 819 136 820 145 821 2 822 81 823 2 824 159 825 160 826 133 827 2 828 194 829 2 830 163 831 26 832 255 833 114 834 55 835 52 836 129 837 98 838 33 839 2 840 174 841 30 842 33 843 26 844 83 845 138 846 129 847 110 848 157 849 34 850 169 851 52 852 147 853 2 854 121 855 142 856 159 857 2 858 128 859 2 860 225 861 142 862 129 863 2 864 301 865 84 866 33 867 74 868 173 869 34 870 186 871 30 872 159 873 88 874 117 875 186 876 205 877 2 878 129 879 74 880 264 881 2 882 243 883 2 884 180 885 100 886 129 887 2 888 327 889 36 890 157 891 186 892 259 893 48 894 267 895 34 896 365 897 78 898 17 899 34 900 124 901 28 902 97 903 102 904 79 905 28 906 71 907 2 908 67 909 92 910 191 911 2 912 191 913 66 914 33 915 108 916 83 917 96 918 178 919 2 920 226 921 26 922 65 923 54 924 295 925 104 926 129 927 94 928 219 929 2 930 131 931 140 932 83 933 74 934 65 935 138 936 286 937 2 938 109 939 74 940 231 941 2 942 223 943 60 944 243 945 278 946 157 947 2 948 201 949 66 950 245 951 56 952 312 953 2 954 247 955 52 956 259 957 160 958 257 959 96 960 449 961 32 962 115 963 188 964 67 965 100 966 282 967 2 968 217 969 216 970 179 971 2 972 317 973 132 974 129 975 198 976 231 977 2 978 79 979 28 980 315 981 34 982 129 983 2 984 267 985 94 986 166 987 82 988 341 989 64 990 389 991 2 992 344 993 26 994 133 995 154 996 169 997 2 998 129 999 100 1000 349