0 1 1 3 2 1 3 7 4 9 5 11 6 13 7 3 8 17 9 19 10 21 11 23 12 1 13 27 14 29 15 31 16 33 17 7 18 37 19 39 20 41 21 43 22 9 23 47 24 49 25 51 26 53 27 11 28 57 29 59 30 61 31 63 32 13 33 67 34 69 35 71 36 73 37 3 38 77 39 79 40 81 41 83 42 17 43 87 44 89 45 91 46 93 47 19 48 97 49 99 50 101 51 103 52 21 53 107 54 109 55 111 56 113 57 23 58 117 59 119 60 121 61 123 62 5 63 127 64 129 65 131 66 133 67 27 68 137 69 139 70 141 71 143 72 29 73 147 74 149 75 151 76 153 77 31 78 157 79 159 80 161 81 163 82 33 83 167 84 169 85 171 86 173 87 7 88 177 89 179 90 181 91 183 92 37 93 187 94 189 95 191 96 193 97 39 98 197 99 199 100 201 101 203 102 41 103 207 104 209 105 211 106 213 107 43 108 217 109 219 110 221 111 223 112 9 113 227 114 229 115 231 116 233 117 47 118 237 119 239 120 241 121 243 122 49 123 247 124 249 125 251 126 253 127 51 128 257 129 259 130 261 131 263 132 53 133 267 134 269 135 271 136 273 137 11 138 277 139 279 140 281 141 283 142 57 143 287 144 289 145 291 146 293 147 59 148 297 149 299 150 301 151 303 152 61 153 307 154 309 155 311 156 313 157 63 158 317 159 319 160 321 161 323 162 13 163 327 164 329 165 331 166 333 167 67 168 337 169 339 170 341 171 343 172 69 173 347 174 349 175 351 176 353 177 71 178 357 179 359 180 361 181 363 182 73 183 367 184 369 185 371 186 373 187 15 188 377 189 379 190 381 191 383 192 77 193 387 194 389 195 391 196 393 197 79 198 397 199 399 200 401 201 403 202 81 203 407 204 409 205 411 206 413 207 83 208 417 209 419 210 421 211 423 212 17 213 427 214 429 215 431 216 433 217 87 218 437 219 439 220 441 221 443 222 89 223 447 224 449 225 451 226 453 227 91 228 457 229 459 230 461 231 463 232 93 233 467 234 469 235 471 236 473 237 19 238 477 239 479 240 481 241 483 242 97 243 487 244 489 245 491 246 493 247 99 248 497 249 499 250 501 251 503 252 101 253 507 254 509 255 511 256 513 257 103 258 517 259 519 260 521 261 523 262 21 263 527 264 529 265 531 266 533 267 107 268 537 269 539 270 541 271 543 272 109 273 547 274 549 275 551 276 553 277 111 278 557 279 559 280 561 281 563 282 113 283 567 284 569 285 571 286 573 287 23 288 577 289 579 290 581 291 583 292 117 293 587 294 589 295 591 296 593 297 119 298 597 299 599 300 601 301 603 302 121 303 607 304 609 305 611 306 613 307 123 308 617 309 619 310 621 311 623 312 25 313 627 314 629 315 631 316 633 317 127 318 637 319 639 320 641 321 643 322 129 323 647 324 649 325 651 326 653 327 131 328 657 329 659 330 661 331 663 332 133 333 667 334 669 335 671 336 673 337 27 338 677 339 679 340 681 341 683 342 137 343 687 344 689 345 691 346 693 347 139 348 697 349 699 350 701 351 703 352 141 353 707 354 709 355 711 356 713 357 143 358 717 359 719 360 721 361 723 362 29 363 727 364 729 365 731 366 733 367 147 368 737 369 739 370 741 371 743 372 149 373 747 374 749 375 751 376 753 377 151 378 757 379 759 380 761 381 763 382 153 383 767 384 769 385 771 386 773 387 31 388 777 389 779 390 781 391 783 392 157 393 787 394 789 395 791 396 793 397 159 398 797 399 799 400 801 401 803 402 161 403 807 404 809 405 811 406 813 407 163 408 817 409 819 410 821 411 823 412 33 413 827 414 829 415 831 416 833 417 167 418 837 419 839 420 841 421 843 422 169 423 847 424 849 425 851 426 853 427 171 428 857 429 859 430 861 431 863 432 173 433 867 434 869 435 871 436 873 437 35 438 877 439 879 440 881 441 883 442 177 443 887 444 889 445 891 446 893 447 179 448 897 449 899 450 901 451 903 452 181 453 907 454 909 455 911 456 913 457 183 458 917 459 919 460 921 461 923 462 37 463 927 464 929 465 931 466 933 467 187 468 937 469 939 470 941 471 943 472 189 473 947 474 949 475 951 476 953 477 191 478 957 479 959 480 961 481 963 482 193 483 967 484 969 485 971 486 973 487 39 488 977 489 979 490 981 491 983 492 197 493 987 494 989 495 991 496 993 497 199 498 997 499 999 500 1001 501 1003 502 201 503 1007 504 1009 505 1011 506 1013 507 203 508 1017 509 1019 510 1021 511 1023 512 41 513 1027 514 1029 515 1031 516 1033 517 207 518 1037 519 1039 520 1041 521 1043 522 209 523 1047 524 1049 525 1051 526 1053 527 211 528 1057 529 1059 530 1061 531 1063 532 213 533 1067 534 1069 535 1071 536 1073 537 43 538 1077 539 1079 540 1081 541 1083 542 217 543 1087 544 1089 545 1091 546 1093 547 219 548 1097 549 1099 550 1101 551 1103 552 221 553 1107 554 1109 555 1111 556 1113 557 223 558 1117 559 1119 560 1121 561 1123 562 45 563 1127 564 1129 565 1131 566 1133 567 227 568 1137 569 1139 570 1141 571 1143 572 229 573 1147 574 1149 575 1151 576 1153 577 231 578 1157 579 1159 580 1161 581 1163 582 233 583 1167 584 1169 585 1171 586 1173 587 47 588 1177 589 1179 590 1181 591 1183 592 237 593 1187 594 1189 595 1191 596 1193 597 239 598 1197 599 1199 600 1201 601 1203 602 241 603 1207 604 1209 605 1211 606 1213 607 243 608 1217 609 1219 610 1221 611 1223 612 49 613 1227 614 1229 615 1231 616 1233 617 247 618 1237 619 1239 620 1241 621 1243 622 249 623 1247 624 1249 625 1251 626 1253 627 251 628 1257 629 1259 630 1261 631 1263 632 253 633 1267 634 1269 635 1271 636 1273 637 51 638 1277 639 1279 640 1281 641 1283 642 257 643 1287 644 1289 645 1291 646 1293 647 259 648 1297 649 1299 650 1301 651 1303 652 261 653 1307 654 1309 655 1311 656 1313 657 263 658 1317 659 1319 660 1321 661 1323 662 53 663 1327 664 1329 665 1331 666 1333 667 267 668 1337 669 1339 670 1341 671 1343 672 269 673 1347 674 1349 675 1351 676 1353 677 271 678 1357 679 1359 680 1361 681 1363 682 273 683 1367 684 1369 685 1371 686 1373 687 55 688 1377 689 1379 690 1381 691 1383 692 277 693 1387 694 1389 695 1391 696 1393 697 279 698 1397 699 1399 700 1401 701 1403 702 281 703 1407 704 1409 705 1411 706 1413 707 283 708 1417 709 1419 710 1421 711 1423 712 57 713 1427 714 1429 715 1431 716 1433 717 287 718 1437 719 1439 720 1441 721 1443 722 289 723 1447 724 1449 725 1451 726 1453 727 291 728 1457 729 1459 730 1461 731 1463 732 293 733 1467 734 1469 735 1471 736 1473 737 59 738 1477 739 1479 740 1481 741 1483 742 297 743 1487 744 1489 745 1491 746 1493 747 299 748 1497 749 1499 750 1501 751 1503 752 301 753 1507 754 1509 755 1511 756 1513 757 303 758 1517 759 1519 760 1521 761 1523 762 61 763 1527 764 1529 765 1531 766 1533 767 307 768 1537 769 1539 770 1541 771 1543 772 309 773 1547 774 1549 775 1551 776 1553 777 311 778 1557 779 1559 780 1561 781 1563 782 313 783 1567 784 1569 785 1571 786 1573 787 63 788 1577 789 1579 790 1581 791 1583 792 317 793 1587 794 1589 795 1591 796 1593 797 319 798 1597 799 1599 800 1601 801 1603 802 321 803 1607 804 1609 805 1611 806 1613 807 323 808 1617 809 1619 810 1621 811 1623 812 65 813 1627 814 1629 815 1631 816 1633 817 327 818 1637 819 1639 820 1641 821 1643 822 329 823 1647 824 1649 825 1651 826 1653 827 331 828 1657 829 1659 830 1661 831 1663 832 333 833 1667 834 1669 835 1671 836 1673 837 67 838 1677 839 1679 840 1681 841 1683 842 337 843 1687 844 1689 845 1691 846 1693 847 339 848 1697 849 1699 850 1701 851 1703 852 341 853 1707 854 1709 855 1711 856 1713 857 343 858 1717 859 1719 860 1721 861 1723 862 69 863 1727 864 1729 865 1731 866 1733 867 347 868 1737 869 1739 870 1741 871 1743 872 349 873 1747 874 1749 875 1751 876 1753 877 351 878 1757 879 1759 880 1761 881 1763 882 353 883 1767 884 1769 885 1771 886 1773 887 71 888 1777 889 1779 890 1781 891 1783 892 357 893 1787 894 1789 895 1791 896 1793 897 359 898 1797 899 1799 900 1801 901 1803 902 361 903 1807 904 1809 905 1811 906 1813 907 363 908 1817 909 1819 910 1821 911 1823 912 73 913 1827 914 1829 915 1831 916 1833 917 367 918 1837 919 1839 920 1841 921 1843 922 369 923 1847 924 1849 925 1851 926 1853 927 371 928 1857 929 1859 930 1861 931 1863 932 373 933 1867 934 1869 935 1871 936 1873 937 75 938 1877 939 1879 940 1881 941 1883 942 377 943 1887 944 1889 945 1891 946 1893 947 379 948 1897 949 1899 950 1901 951 1903 952 381 953 1907 954 1909 955 1911 956 1913 957 383 958 1917 959 1919 960 1921 961 1923 962 77 963 1927 964 1929 965 1931 966 1933 967 387 968 1937 969 1939 970 1941 971 1943 972 389 973 1947 974 1949 975 1951 976 1953 977 391 978 1957 979 1959 980 1961 981 1963 982 393 983 1967 984 1969 985 1971 986 1973 987 79 988 1977 989 1979 990 1981 991 1983 992 397 993 1987 994 1989 995 1991 996 1993 997 399 998 1997 999 1999 1000 2001 1001 2003 1002 401 1003 2007 1004 2009 1005 2011 1006 2013 1007 403 1008 2017 1009 2019 1010 2021 1011 2023 1012 81 1013 2027 1014 2029 1015 2031 1016 2033 1017 407 1018 2037 1019 2039 1020 2041 1021 2043 1022 409 1023 2047 1024 2049 1025 2051 1026 2053 1027 411 1028 2057 1029 2059 1030 2061 1031 2063 1032 413 1033 2067 1034 2069 1035 2071 1036 2073 1037 83 1038 2077 1039 2079 1040 2081 1041 2083 1042 417 1043 2087 1044 2089 1045 2091 1046 2093 1047 419 1048 2097 1049 2099 1050 2101 1051 2103 1052 421 1053 2107 1054 2109 1055 2111 1056 2113 1057 423 1058 2117 1059 2119 1060 2121 1061 2123 1062 85 1063 2127 1064 2129 1065 2131 1066 2133 1067 427 1068 2137 1069 2139 1070 2141 1071 2143 1072 429 1073 2147 1074 2149 1075 2151 1076 2153 1077 431 1078 2157 1079 2159 1080 2161 1081 2163 1082 433 1083 2167 1084 2169 1085 2171 1086 2173 1087 87 1088 2177 1089 2179 1090 2181 1091 2183 1092 437 1093 2187 1094 2189 1095 2191 1096 2193 1097 439 1098 2197 1099 2199 1100 2201 1101 2203 1102 441 1103 2207 1104 2209 1105 2211 1106 2213 1107 443 1108 2217 1109 2219 1110 2221 1111 2223 1112 89 1113 2227 1114 2229 1115 2231 1116 2233 1117 447 1118 2237 1119 2239 1120 2241 1121 2243 1122 449 1123 2247 1124 2249 1125 2251 1126 2253 1127 451 1128 2257 1129 2259 1130 2261 1131 2263 1132 453 1133 2267 1134 2269 1135 2271 1136 2273 1137 91 1138 2277 1139 2279 1140 2281 1141 2283 1142 457 1143 2287 1144 2289 1145 2291 1146 2293 1147 459 1148 2297 1149 2299 1150 2301 1151 2303 1152 461 1153 2307 1154 2309 1155 2311 1156 2313 1157 463 1158 2317 1159 2319 1160 2321 1161 2323 1162 93 1163 2327 1164 2329 1165 2331 1166 2333 1167 467 1168 2337 1169 2339 1170 2341 1171 2343 1172 469 1173 2347 1174 2349 1175 2351 1176 2353 1177 471 1178 2357 1179 2359 1180 2361 1181 2363 1182 473 1183 2367 1184 2369 1185 2371 1186 2373 1187 95 1188 2377 1189 2379 1190 2381 1191 2383 1192 477 1193 2387 1194 2389 1195 2391 1196 2393 1197 479 1198 2397 1199 2399 1200 2401 1201 2403 1202 481 1203 2407 1204 2409 1205 2411 1206 2413 1207 483 1208 2417 1209 2419 1210 2421 1211 2423 1212 97 1213 2427 1214 2429 1215 2431 1216 2433 1217 487 1218 2437 1219 2439 1220 2441 1221 2443 1222 489 1223 2447 1224 2449 1225 2451 1226 2453 1227 491 1228 2457 1229 2459 1230 2461 1231 2463 1232 493 1233 2467 1234 2469 1235 2471 1236 2473 1237 99 1238 2477 1239 2479 1240 2481 1241 2483 1242 497 1243 2487 1244 2489 1245 2491 1246 2493 1247 499 1248 2497 1249 2499 1250 2501 1251 2503 1252 501 1253 2507 1254 2509 1255 2511 1256 2513 1257 503 1258 2517 1259 2519 1260 2521 1261 2523 1262 101 1263 2527 1264 2529 1265 2531 1266 2533 1267 507 1268 2537 1269 2539 1270 2541 1271 2543 1272 509 1273 2547 1274 2549 1275 2551 1276 2553 1277 511 1278 2557 1279 2559 1280 2561 1281 2563 1282 513 1283 2567 1284 2569 1285 2571 1286 2573 1287 103 1288 2577 1289 2579 1290 2581 1291 2583 1292 517 1293 2587 1294 2589 1295 2591 1296 2593 1297 519 1298 2597 1299 2599 1300 2601 1301 2603 1302 521 1303 2607 1304 2609 1305 2611 1306 2613 1307 523 1308 2617 1309 2619 1310 2621 1311 2623 1312 105 1313 2627 1314 2629 1315 2631 1316 2633 1317 527 1318 2637 1319 2639 1320 2641 1321 2643 1322 529 1323 2647 1324 2649 1325 2651 1326 2653 1327 531 1328 2657 1329 2659 1330 2661 1331 2663 1332 533 1333 2667 1334 2669 1335 2671 1336 2673 1337 107 1338 2677 1339 2679 1340 2681 1341 2683 1342 537 1343 2687 1344 2689 1345 2691 1346 2693 1347 539 1348 2697 1349 2699 1350 2701 1351 2703 1352 541 1353 2707 1354 2709 1355 2711 1356 2713 1357 543 1358 2717 1359 2719 1360 2721 1361 2723 1362 109 1363 2727 1364 2729 1365 2731 1366 2733 1367 547 1368 2737 1369 2739 1370 2741 1371 2743 1372 549 1373 2747 1374 2749 1375 2751 1376 2753 1377 551 1378 2757 1379 2759 1380 2761 1381 2763 1382 553 1383 2767 1384 2769 1385 2771 1386 2773 1387 111 1388 2777 1389 2779 1390 2781 1391 2783 1392 557 1393 2787 1394 2789 1395 2791 1396 2793 1397 559 1398 2797 1399 2799 1400 2801 1401 2803 1402 561 1403 2807 1404 2809 1405 2811 1406 2813 1407 563 1408 2817 1409 2819 1410 2821 1411 2823 1412 113 1413 2827 1414 2829 1415 2831 1416 2833 1417 567 1418 2837 1419 2839 1420 2841 1421 2843 1422 569 1423 2847 1424 2849 1425 2851 1426 2853 1427 571 1428 2857 1429 2859 1430 2861 1431 2863 1432 573 1433 2867 1434 2869 1435 2871 1436 2873 1437 115 1438 2877 1439 2879 1440 2881 1441 2883 1442 577 1443 2887 1444 2889 1445 2891 1446 2893 1447 579 1448 2897 1449 2899 1450 2901 1451 2903 1452 581 1453 2907 1454 2909 1455 2911 1456 2913 1457 583 1458 2917 1459 2919 1460 2921 1461 2923 1462 117 1463 2927 1464 2929 1465 2931 1466 2933 1467 587 1468 2937 1469 2939 1470 2941 1471 2943 1472 589 1473 2947 1474 2949 1475 2951 1476 2953 1477 591 1478 2957 1479 2959 1480 2961 1481 2963 1482 593 1483 2967 1484 2969 1485 2971 1486 2973 1487 119 1488 2977 1489 2979 1490 2981 1491 2983 1492 597 1493 2987 1494 2989 1495 2991 1496 2993 1497 599 1498 2997 1499 2999 1500 3001 1501 3003 1502 601 1503 3007 1504 3009 1505 3011 1506 3013 1507 603 1508 3017 1509 3019 1510 3021 1511 3023 1512 121 1513 3027 1514 3029 1515 3031 1516 3033 1517 607 1518 3037 1519 3039 1520 3041 1521 3043 1522 609 1523 3047 1524 3049 1525 3051 1526 3053 1527 611 1528 3057 1529 3059 1530 3061 1531 3063 1532 613 1533 3067 1534 3069 1535 3071 1536 3073 1537 123 1538 3077 1539 3079 1540 3081 1541 3083 1542 617 1543 3087 1544 3089 1545 3091 1546 3093 1547 619 1548 3097 1549 3099 1550 3101 1551 3103 1552 621 1553 3107 1554 3109 1555 3111 1556 3113 1557 623 1558 3117 1559 3119 1560 3121 1561 3123 1562 125 1563 3127 1564 3129 1565 3131 1566 3133 1567 627 1568 3137 1569 3139 1570 3141 1571 3143 1572 629 1573 3147 1574 3149 1575 3151 1576 3153 1577 631 1578 3157 1579 3159 1580 3161 1581 3163 1582 633 1583 3167 1584 3169 1585 3171 1586 3173 1587 127 1588 3177 1589 3179 1590 3181 1591 3183 1592 637 1593 3187 1594 3189 1595 3191 1596 3193 1597 639 1598 3197 1599 3199 1600 3201 1601 3203 1602 641 1603 3207 1604 3209 1605 3211 1606 3213 1607 643 1608 3217 1609 3219 1610 3221 1611 3223 1612 129 1613 3227 1614 3229 1615 3231 1616 3233 1617 647 1618 3237 1619 3239 1620 3241 1621 3243 1622 649 1623 3247 1624 3249 1625 3251 1626 3253 1627 651 1628 3257 1629 3259 1630 3261 1631 3263 1632 653 1633 3267 1634 3269 1635 3271 1636 3273 1637 131 1638 3277 1639 3279 1640 3281 1641 3283 1642 657 1643 3287 1644 3289 1645 3291 1646 3293 1647 659 1648 3297 1649 3299 1650 3301 1651 3303 1652 661 1653 3307 1654 3309 1655 3311 1656 3313 1657 663 1658 3317 1659 3319 1660 3321 1661 3323 1662 133 1663 3327 1664 3329 1665 3331 1666 3333 1667 667 1668 3337 1669 3339 1670 3341 1671 3343 1672 669 1673 3347 1674 3349 1675 3351 1676 3353 1677 671 1678 3357 1679 3359 1680 3361 1681 3363 1682 673 1683 3367 1684 3369 1685 3371 1686 3373 1687 135 1688 3377 1689 3379 1690 3381 1691 3383 1692 677 1693 3387 1694 3389 1695 3391 1696 3393 1697 679 1698 3397 1699 3399 1700 3401 1701 3403 1702 681 1703 3407 1704 3409 1705 3411 1706 3413 1707 683 1708 3417 1709 3419 1710 3421 1711 3423 1712 137 1713 3427 1714 3429 1715 3431 1716 3433 1717 687 1718 3437 1719 3439 1720 3441 1721 3443 1722 689 1723 3447 1724 3449 1725 3451 1726 3453 1727 691 1728 3457 1729 3459 1730 3461 1731 3463 1732 693 1733 3467 1734 3469 1735 3471 1736 3473 1737 139 1738 3477 1739 3479 1740 3481 1741 3483 1742 697 1743 3487 1744 3489 1745 3491 1746 3493 1747 699 1748 3497 1749 3499 1750 3501 1751 3503 1752 701 1753 3507 1754 3509 1755 3511 1756 3513 1757 703 1758 3517 1759 3519 1760 3521 1761 3523 1762 141 1763 3527 1764 3529 1765 3531 1766 3533 1767 707 1768 3537 1769 3539 1770 3541 1771 3543 1772 709 1773 3547 1774 3549 1775 3551 1776 3553 1777 711 1778 3557 1779 3559 1780 3561 1781 3563 1782 713 1783 3567 1784 3569 1785 3571 1786 3573 1787 143 1788 3577 1789 3579 1790 3581 1791 3583 1792 717 1793 3587 1794 3589 1795 3591 1796 3593 1797 719 1798 3597 1799 3599 1800 3601 1801 3603 1802 721 1803 3607 1804 3609 1805 3611 1806 3613 1807 723 1808 3617 1809 3619 1810 3621 1811 3623 1812 145 1813 3627 1814 3629 1815 3631 1816 3633 1817 727 1818 3637 1819 3639 1820 3641 1821 3643 1822 729 1823 3647 1824 3649 1825 3651 1826 3653 1827 731 1828 3657 1829 3659 1830 3661 1831 3663 1832 733 1833 3667 1834 3669 1835 3671 1836 3673 1837 147 1838 3677 1839 3679 1840 3681 1841 3683 1842 737 1843 3687 1844 3689 1845 3691 1846 3693 1847 739 1848 3697 1849 3699 1850 3701 1851 3703 1852 741 1853 3707 1854 3709 1855 3711 1856 3713 1857 743 1858 3717 1859 3719 1860 3721 1861 3723 1862 149 1863 3727 1864 3729 1865 3731 1866 3733 1867 747 1868 3737 1869 3739 1870 3741 1871 3743 1872 749 1873 3747 1874 3749 1875 3751 1876 3753 1877 751 1878 3757 1879 3759 1880 3761 1881 3763 1882 753 1883 3767 1884 3769 1885 3771 1886 3773 1887 151 1888 3777 1889 3779 1890 3781 1891 3783 1892 757 1893 3787 1894 3789 1895 3791 1896 3793 1897 759 1898 3797 1899 3799 1900 3801 1901 3803 1902 761 1903 3807 1904 3809 1905 3811 1906 3813 1907 763 1908 3817 1909 3819 1910 3821 1911 3823 1912 153 1913 3827 1914 3829 1915 3831 1916 3833 1917 767 1918 3837 1919 3839 1920 3841 1921 3843 1922 769 1923 3847 1924 3849 1925 3851 1926 3853 1927 771 1928 3857 1929 3859 1930 3861 1931 3863 1932 773 1933 3867 1934 3869 1935 3871 1936 3873 1937 155 1938 3877 1939 3879 1940 3881 1941 3883 1942 777 1943 3887 1944 3889 1945 3891 1946 3893 1947 779 1948 3897 1949 3899 1950 3901 1951 3903 1952 781 1953 3907 1954 3909 1955 3911 1956 3913 1957 783 1958 3917 1959 3919 1960 3921 1961 3923 1962 157 1963 3927 1964 3929 1965 3931 1966 3933 1967 787 1968 3937 1969 3939 1970 3941 1971 3943 1972 789 1973 3947 1974 3949 1975 3951 1976 3953 1977 791 1978 3957 1979 3959 1980 3961 1981 3963 1982 793 1983 3967 1984 3969 1985 3971 1986 3973 1987 159 1988 3977 1989 3979 1990 3981 1991 3983 1992 797 1993 3987 1994 3989 1995 3991 1996 3993 1997 799 1998 3997 1999 3999 2000 4001