1 1 2 2 3 3 4 5 5 4 6 7 7 6 8 9 9 13 10 8 11 10 12 19 13 14 14 12 15 29 16 16 17 21 18 22 19 37 20 18 21 27 22 20 23 43 24 33 25 34 26 28 27 49 28 24 29 61 30 32 31 67 32 30 33 73 34 45 35 57 36 44 37 40 38 36 39 50 40 42 41 52 42 101 43 63 44 85 45 109 46 91 47 74 48 54 49 81 50 48 51 68 52 64 53 93 54 86 55 121 56 137 57 76 58 66 59 149 60 111 61 99 62 157 63 133 64 106 65 163 66 60 67 98 68 173 69 129 70 88 71 117 72 169 73 80 74 105 75 193 76 72 77 197 78 199 79 134 80 104 81 211 82 102 83 100 84 146 85 84 86 147 87 229 88 90 89 114 90 241 91 112 92 96 93 128 94 217 95 257 96 171 97 215 98 148 99 136 100 201 101 277 102 108 103 281 104 283 105 138 106 164 107 219 108 152 109 259 110 202 111 289 112 172 113 126 114 313 115 317 116 189 117 170 118 218 119 331 120 132 121 337 122 226 123 347 124 349 125 301 126 353 127 120 128 162 129 243 130 367 131 150 132 373 133 160 134 379 135 361 136 186 137 261 138 156 139 262 140 397 141 196 142 343 143 401 144 144 145 303 146 409 147 274 148 279 149 236 150 421 151 230 152 208 153 327 154 365 155 273 156 232 157 222 158 457 159 461 160 463 161 200 162 198 163 314 164 268 165 168 166 487 167 326 168 333 169 427 170 499 171 204 172 192 173 509 174 256 175 381 176 292 177 346 178 523 179 258 180 363 181 290 182 541 183 469 184 180 185 547 186 338 187 411 188 529 189 272 190 228 191 563 192 296 193 387 194 210 195 577 196 386 197 260 198 511 199 394 200 216 201 601 202 453 203 505 204 613 205 559 206 617 207 304 208 315 209 328 210 471 211 422 212 399 213 641 214 643 215 318 216 653 217 489 218 344 219 661 220 276 221 673 222 677 223 294 224 388 225 458 226 691 227 519 228 306 229 709 230 404 231 264 232 405 233 252 234 507 235 733 236 739 237 441 238 240 239 751 240 340 241 757 242 703 243 320 244 434 245 436 246 514 247 579 248 342 249 625 250 364 251 787 252 430 253 452 254 513 255 549 256 424 257 811 258 402 259 288 260 821 261 823 262 685 263 829 264 721 265 554 266 312 267 562 268 324 269 633 270 566 271 853 272 392 273 857 274 859 275 330 276 300 277 841 278 877 279 763 280 416 281 603 282 438 283 372 284 472 285 907 286 518 287 687 288 578 289 524 290 464 291 484 292 414 293 937 294 626 295 785 296 871 297 634 298 378 299 400 300 657 301 548 302 567 303 530 304 977 305 556 306 815 307 336 308 961 309 662 310 997 311 390 312 1009 313 674 314 448 315 384 316 1021 317 512 318 651 319 490 320 771 321 1033 322 949 323 711 324 694 325 596 326 1051 327 602 328 706 329 444 330 1069 331 408 332 813 333 396 334 729 335 1093 336 845 337 734 338 628 339 584 340 831 341 550 342 1117 343 532 344 746 345 1123 346 843 347 1129 348 544 349 849 350 758 351 722 352 652 353 462 354 1153 355 965 356 360 357 1171 358 492 359 592 360 1181 361 985 362 794 363 456 364 1201 365 802 366 450 367 1213 368 777 369 692 370 606 371 867 372 818 373 516 374 1237 375 432 376 558 377 1249 378 939 379 520 380 1099 381 842 382 951 383 468 384 1277 385 837 386 676 387 1283 388 1289 389 1291 390 510 391 1297 392 650 393 1303 394 1307 395 1141 396 654 397 1321 398 909 399 993 400 730 401 420 402 712 403 927 404 772 405 1273 406 1361 407 688 408 678 409 1261 410 914 411 1145 412 1381 413 788 414 926 415 796 416 765 417 1369 418 903 419 1409 420 1059 421 1423 422 1313 423 981 424 1433 425 552 426 1447 427 891 428 1453 429 819 430 1459 431 974 432 776 433 1101 434 982 435 1387 436 666 437 844 438 528 439 1489 440 1493 441 1119 442 998 443 480 444 999 445 704 446 640 447 1531 448 762 449 1417 450 1543 451 1285 452 1549 453 1351 454 1553 455 504 456 1042 457 892 458 1046 459 1579 460 786 461 1191 462 588 463 1597 464 1029 465 1601 466 1203 467 916 468 1613 469 680 470 1621 471 1082 472 1627 473 938 474 612 475 1227 476 1094 477 872 478 576 479 822 480 1657 481 1058 482 1143 483 1385 484 1669 485 1591 486 848 487 540 488 1263 489 1126 490 964 491 1477 492 1697 493 1699 494 1415 495 904 496 774 497 1721 498 1681 499 1723 500 690 501 1089 502 1154 503 624 504 1741 505 1747 506 1753 507 1161 508 820 509 784 510 1022 511 832 512 1186 513 1783 514 1787 515 1789 516 868 517 1233 518 696 519 1801 520 1028 521 1811 522 648 523 684 524 906 525 1371 526 1010 527 1603 528 1226 529 860 530 1234 531 1389 532 600 533 1573 534 1867 535 630 536 1873 537 1877 538 1879 539 1565 540 928 541 1849 542 942 543 1901 544 804 545 1585 546 1913 547 744 548 976 549 1282 550 1286 551 1933 552 1687 553 1070 554 1108 555 1341 556 1461 557 800 558 988 559 1306 560 978 561 1124 562 1359 563 1048 564 1281 565 1322 566 1132 567 1655 568 1993 569 968 570 1997 571 1497 572 2003 573 2011 574 660 575 2017 576 1346 577 1125 578 2029 579 1354 580 896 581 768 582 1024 583 1078 584 1413 585 1172 586 1799 587 1096 588 876 589 1382 590 1197 591 2081 592 2083 593 1038 594 2089 595 1569 596 1112 597 954 598 1072 599 1419 600 2113 601 1765 602 1036 603 1418 604 1467 605 2137 606 2141 607 2143 608 1156 609 2153 610 1228 611 870 612 2161 613 1813 614 1623 615 1407 616 810 617 2179 618 828 619 1641 620 1014 621 1252 622 2071 623 1466 624 2203 625 1835 626 1587 627 2213 628 1478 629 2221 630 882 631 1939 632 1268 633 816 634 2237 635 756 636 1865 637 1192 638 2251 639 1502 640 2209 641 1557 642 1060 643 2269 644 1981 645 1514 646 888 647 2281 648 1088 649 1713 650 1168 651 2119 652 2297 653 930 654 1538 655 1731 656 1546 657 1324 658 1158 659 2333 660 792 661 2341 662 1250 663 2347 664 780 665 2257 666 2357 667 1574 668 1348 669 1533 670 1256 671 2371 672 1182 673 2377 674 1521 675 2197 676 2381 677 2383 678 1985 679 2389 680 980 681 1026 682 1803 683 2005 684 720 685 1539 686 2423 687 1618 688 1821 689 1388 690 2437 691 2441 692 1414 693 1396 694 1839 695 1304 696 1204 697 1642 698 2467 699 1646 700 2473 701 1412 702 912 703 1370 704 1658 705 1395 706 2503 707 2107 708 2191 709 864 710 1737 711 1893 712 2105 713 1216 714 1266 715 972 716 2549 717 2551 718 2557 719 1659 720 1706 721 1923 722 1714 723 1468 724 1718 725 2479 726 1122 727 2593 728 1791 729 1040 730 1384 731 1682 732 1959 733 1492 734 2621 735 1754 736 1032 737 1312 738 1983 739 1206 740 2317 741 2657 742 1516 743 1606 744 1444 745 2671 746 2677 747 2683 748 924 749 2689 750 2693 751 2019 752 1160 753 2359 754 2707 755 2031 756 2713 757 2509 758 1809 759 1814 760 2623 761 936 762 2731 763 1110 764 2741 765 1164 766 1352 767 2285 768 2749 769 2753 770 1899 771 1374 772 2073 773 1376 774 2777 775 2315 776 1588 777 1424 778 2791 779 2797 780 1372 781 2401 782 2801 783 2803 784 990 785 2701 786 1604 787 2819 788 900 789 1882 790 2471 791 2833 792 2837 793 2127 794 1570 795 2851 796 1212 797 2857 798 1906 799 2809 800 1636 801 840 802 1314 803 2887 804 2897 805 1134 806 1544 807 1116 808 1802 809 2917 810 2435 811 1954 812 2199 813 1508 814 2569 815 1630 816 1684 817 2957 818 1971 819 1665 820 2743 821 1576 822 2971 823 1050 824 1922 825 2061 826 2611 827 1994 828 1592 829 3001 830 2253 831 3011 832 3019 833 1020 834 2018 835 2271 836 1300 837 2109 838 2026 839 960 840 3049 841 1408 842 3061 843 1280 844 3067 845 1302 846 1666 847 1308 848 3083 849 3089 850 1542 851 2066 852 1460 853 3109 854 1422 855 3121 856 1875 857 1730 858 1092 859 3137 860 2615 861 2169 862 1796 863 2361 864 2102 865 2983 866 1616 867 3163 868 1290 869 3169 870 1688 871 3181 872 2779 873 2122 874 3187 875 1356 876 2133 877 3203 878 1828 879 2138 880 2807 881 3217 882 2977 883 3221 884 1008 885 3229 886 1844 887 1272 888 1852 889 2705 890 3253 891 3139 892 3257 893 3259 894 1626 895 3271 896 1170 897 1458 898 2187 899 2186 900 2463 901 1690 902 2469 903 3161 904 3301 905 3307 906 1918 907 3313 908 1152 909 2645 910 2487 911 3323 912 1953 913 2218 914 3331 915 1662 916 3343 917 1360 918 2234 919 1140 920 3361 921 2246 922 3373 923 2947 924 1686 925 3133 926 2258 927 3391 928 1696 929 1698 930 1744 931 3413 932 1948 933 1176 934 1935 935 3433 936 2577 937 1964 938 1832 939 1410 940 1332 941 2306 942 3463 943 2885 944 3469 945 1456 946 3287 947 2523 948 1930 949 1996 950 1224 951 2631 952 2342 953 3517 954 2289 955 1248 956 3529 957 1808 958 2439 959 3539 960 3481 961 3541 962 2362 963 3547 964 2409 965 3557 966 3559 967 1970 968 1664 969 3571 970 2386 971 1524 972 1568 973 3593 974 1080 975 2402 976 3607 977 3005 978 2493 979 3617 980 3623 981 1928 982 2721 983 3637 984 2223 985 2426 986 3643 987 1554 988 2084 989 3211 990 3199 991 2529 992 2092 993 2222 994 3673 995 3677 996 2757 997 1734 998 2458 999 2547 1000 1572