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