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