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