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