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