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