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