0 2 1 2 2 2 3 2 4 3 5 2 6 3 7 3 8 7 9 3 10 3 11 5 12 2 13 3 14 13 15 7 16 31 17 5 18 2 19 7 20 17 21 67 22 41 23 3 24 13 25 3 26 43 27 17 28 97 29 7 30 29 31 109 32 3 33 71 34 5 35 2 36 7 37 41 38 3 39 59 40 3 41 11 42 29 43 7 44 107 45 67 46 79 47 3 48 743 49 149 50 163 51 2 52 211 53 2 54 19 55 71 56 73 57 23 58 37 59 113 60 149 61 67 62 41 63 617 64 107 65 37 66 107 67 283 68 113 69 19 70 239 71 107 72 73 73 97 74 5 75 43 76 101 77 31 78 2 79 193 80 29 81 193 82 199 83 47 84 71 85 19 86 457 87 17 88 331 89 149 90 257 91 173 92 17 93 457 94 113 95 109 96 3 97 139 98 41 99 317 100 139 101 149 102 353 103 47 104 83 105 373 106 23 107 41 108 31 109 19 110 853 111 71 112 1499 113 179 114 311 115 37 116 23 117 449 118 11 119 443 120 461 121 661 122 617 123 67 124 151 125 79 126 101 127 953 128 389 129 167 130 167 131 47 132 163 133 47 134 2293 135 307 136 5 137 47 138 353 139 71 140 149 141 677 142 53 143 97 144 359 145 431 146 733 147 1471 148 97 149 149 150 113 151 151 152 149 153 43 154 149 155 5 156 71 157 457 158 7 159 3313 160 7 161 11 162 59 163 79 164 643 165 79 166 139 167 137 168 599 169 227 170 83 171 17 172 107 173 29 174 857 175 11 176 1163 177 251 178 2113 179 103 180 61 181 547 182 683 183 373 184 857 185 181 186 31 187 397 188 2243 189 883 190 859 191 109 192 173 193 1087 194 907 195 953 196 523 197 197 198 1091 199 211 200 467 201 211 202 487 203 7 204 1249 205 139 206 71 207 709 208 19 209 2 210 641 211 167 212 317 213 11 214 1093 215 79 216 179 217 1291 218 1151 219 233 220 163 221 307 222 281 223 19 224 541 225 1129 226 313 227 29 228 41 229 113 230 211 231 1103 232 331 233 1373 234 37 235 1321 236 727 237 857 238 173 239 127 240 1013 241 103 242 1531 243 1117 244 439 245 1091 246 157 247 157 248 1321 249 607 250 907 251 661 252 367 253 1871 254 263 255 479 256 499 257 2521 258 491 259 5 260 761 261 463 262 499 263 227 264 257 265 1289 266 359 267 19 268 31 269 467 270 47 271 5 272 41 273 487 274 811 275 431 276 331 277 1657 278 61 279 211 280 929 281 331 282 13 283 727 284 191 285 163 286 53 287 2389 288 139 289 463 290 5 291 293 292 991 293 509 294 271 295 47 296 1723 297 3253 298 2333 299 467 300 67 301 71 302 521 303 11 304 1373 305 107 306 677 307 1559 308 1031 309 3499 310 211 311 83 312 1217 313 1721 314 1609 315 67 316 167 317 401 318 1471 319 349 320 1831 321 2657 322 89 323 241 324 1583 325 389 326 1427 327 61 328 2447 329 683 330 151 331 2129 332 1291 333 2273 334 941 335 151 336 1429 337 467 338 2309 339 967 340 1087 341 163 342 823 343 31 344 43 345 1123 346 2447 347 281 348 461 349 167 350 751 351 2309 352 5 353 197 354 1759 355 409 356 349 357 47 358 43 359 131 360 149 361 503 362 4651 363 691 364 179 365 29 366 151 367 1721 368 1277 369 1601 370 2287 371 599 372 263 373 139 374 191 375 2029 376 173 377 2963 378 1559 379 463 380 1471 381 2903 382 631 383 61 384 2389 385 953 386 997 387 83 388 653 389 53 390 3863 391 67 392 277 393 71 394 563 395 1453 396 2 397 149 398 439 399 241 400 467 401 1229 402 2063 403 1069 404 757 405 1453 406 4099 407 617 408 181 409 1297 410 487 411 3109 412 337 413 3011 414 311 415 23 416 397 417 1021 418 997 419 499 420 647 421 5167 422 1231 423 4099 424 1549 425 2647 426 1777 427 2777 428 2699 429 2417 430 541 431 167 432 7 433 409 434 557 435 3643 436 883 437 839 438 419 439 503 440 43 441 163 442 1087 443 733 444 457 445 1129 446 379 447 4493 448 349 449 1543 450 953 451 3461 452 257 453 2087 454 2003 455 631 456 4889 457 173 458 479 459 1009 460 2753 461 197 462 3019 463 691 464 653 465 157 466 173 467 557 468 2129 469 1019 470 593 471 1381 472 1321 473 1297 474 1021 475 1277 476 4349 477 293 478 283 479 5 480 457 481 83 482 19 483 73 484 443 485 1187 486 419 487 2029 488 67 489 863 490 1307 491 191 492 2693 493 2797 494 5 495 3313 496 4289 497 2851 498 877 499 2467 500 809 501 487 502 443 503 79 504 653 505 107 506 293 507 3319 508 101 509 757 510 1163 511 4483 512 17 513 773 514 397 515 173 516 857 517 11 518 757 519 3067 520 3061 521 757 522 1459 523 557 524 491 525 167 526 4673 527 4931 528 13 529 227 530 3529 531 3307 532 4507 533 587 534 251 535 337 536 6911 537 1231 538 5261 539 3181 540 3691 541 701 542 643 543 863 544 877 545 2039 546 67 547 173 548 101 549 503 550 1013 551 241 552 1999 553 2833 554 10391 555 103 556 1301 557 67 558 1453 559 211 560 3677 561 1217 562 149 563 4421 564 449 565 3209 566 3659 567 6203 568 4217 569 13 570 1049 571 971 572 6719 573 1303 574 2179 575 3181 576 2297 577 2473 578 1117 579 1061 580 317 581 1999 582 619 583 131 584 1237 585 3089 586 2753 587 1427 588 3389 589 1613 590 1291 591 4217 592 1303 593 179 594 733 595 4597 596 1213 597 10861 598 1777 599 2131 600 863 601 3461 602 41 603 167 604 113 605 109 606 317 607 2243 608 3631 609 9013 610 2521 611 1151 612 557 613 5843 614 1999 615 883 616 1579 617 13001 618 101 619 1583 620 137 621 5081 622 10457 623 2141 624 1109 625 2671 626 269 627 239 628 701 629 317 630 2609 631 103 632 2297 633 3697 634 827 635 1021 636 4637 637 4421 638 3253 639 607 640 19 641 2551 642 3989 643 1439 644 2837 645 139 646 503 647 71 648 991 649 431 650 3049 651 617 652 733 653 2309 654 1733 655 29 656 409 657 7489 658 787 659 971 660 983 661 73 662 3851 663 67 664 3931 665 541 666 229 667 569 668 31 669 223 670 101 671 503 672 173 673 937 674 269 675 61 676 2347 677 5 678 131 679 10321 680 4423 681 1697 682 3571 683 277 684 7499 685 79 686 47 687 757 688 2281 689 1627 690 3643 691 491 692 349 693 6421 694 1553 695 3389 696 2437 697 1637 698 853 699 1171 700 2027 701 443 702 571 703 1289 704 479 705 6997 706 4673 707 47 708 1117 709 1607 710 5023 711 857 712 4217 713 59 714 701 715 1583 716 7607 717 1861 718 6301 719 1097 720 1283 721 7829 722 1693 723 577 724 2503 725 433 726 9851 727 2789 728 1973 729 6247 730 2137 731 503 732 4481 733 2203 734 211 735 773 736 457 737 1297 738 3793 739 431 740 293 741 349 742 5881 743 4657 744 2239 745 4523 746 673 747 7393 748 103 749 2357 750 1321 751 439 752 10567 753 9547 754 2551 755 137 756 3929 757 83 758 2969 759 571 760 1601 761 1291 762 2069 763 317 764 5807 765 2693 766 6359 767 2791 768 3767 769 2659 770 2437 771 1993 772 367 773 1861 774 347 775 739 776 5 777 1321 778 1451 779 239 780 991 781 131 782 3911 783 4993 784 2389 785 5407 786 1201 787 7369 788 4567 789 257 790 257 791 3079 792 5903 793 97 794 1487 795 1873 796 2647 797 823 798 379 799 887 800 3761 801 4271 802 2719 803 6379 804 1973 805 1259 806 7309 807 4673 808 6803 809 43 810 1399 811 827 812 2083 813 1303 814 5501 815 4273 816 3319 817 4421 818 2393 819 3911 820 7499 821 1153 822 461 823 8753 824 7079 825 5297 826 12041 827 4001 828 4909 829 3329 830 2381 831 751 832 2659 833 1801 834 1601 835 2393 836 1361 837 3313 838 2273 839 1013 840 263 841 11677 842 823 843 811 844 911 845 919 846 2851 847 8209 848 13397 849 1019 850 1297 851 757 852 8209 853 4861 854 5749 855 19 856 2707 857 3911 858 2069 859 1307 860 2969 861 653 862 5 863 1409 864 7237 865 2591 866 727 867 997 868 467 869 5399 870 8419 871 281 872 1579 873 1381 874 73 875 2339 876 509 877 6311 878 2459 879 2063 880 5407 881 1759 882 3851 883 557 884 3217 885 499 886 5003 887 359 888 1789 889 8971 890 9049 891 3581 892 409 893 1091 894 1277 895 29 896 6659 897 47 898 577 899 439 900 821 901 17 902 2251 903 4663 904 3929 905 733 906 3217 907 8761 908 1901 909 7 910 1753 911 1597 912 3251 913 863 914 6701 915 349 916 4397 917 1109 918 1049 919 6269 920 2017 921 5 922 8353 923 10477 924 449 925 3209 926 17 927 3547 928 19079 929 7927 930 2609 931 1999 932 5 933 197 934 8171 935 6961 936 2687 937 7283 938 12917 939 719 940 13691 941 7477 942 367 943 479 944 2099 945 197 946 1061 947 167 948 2633 949 523 950 9743 951 29 952 2971 953 727 954 823 955 67 956 41 957 2311 958 3797 959 773 960 16487 961 1289 962 1123 963 823 964 199 965 59 966 199 967 461 968 139 969 271 970 1201 971 5231 972 4733 973 2153 974 6361 975 359 976 7297 977 47 978 6287 979 2029 980 9187 981 31 982 7877 983 1931 984 11071 985 8293 986 71 987 151 988 5003 989 563 990 2677 991 311 992 10433 993 281 994 14929 995 9833 996 419 997 43 998 997 999 1213 1000 4219