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