12 1 3003 1 2 5 1 7 10 3 12 4 15 18 6 20 21 8 25 9 27 30 11 32 33 13 35 14 39 16 42 17 44 47 19 50 52 22 54 23 56 24 59 60 26 64 28 66 29 68 49 38 31 73 74 77 34 79 36 81 37 83 85 86 40 88 41 92 43 95 45 97 46 99 48 101 71 103 51 105 108 53 111 55 113 57 115 58 117 118 61 120 62 122 63 126 127 65 131 67 133 69 135 70 137 72 139 75 141 76 143 146 78 148 151 80 154 82 157 84 125 161 87 163 89 165 90 167 91 169 170 93 172 94 176 96 179 98 181 100 184 102 186 104 189 106 191 107 193 147 109 197 110 199 202 203 112 208 209 114 213 214 116 218 221 119 223 121 225 123 227 124 175 229 128 231 129 233 130 237 238 132 243 134 246 136 248 251 138 253 254 140 257 142 259 144 261 145 263 265 267 149 269 150 271 206 188 152 275 153 278 281 283 155 285 156 289 290 158 292 159 296 160 298 301 162 304 164 307 166 310 168 313 171 315 173 317 174 319 314 241 323 177 325 178 328 331 180 334 337 182 339 183 341 344 185 204 346 187 348 350 190 353 192 355 194 357 195 359 196 361 198 362 200 364 201 366 368 370 205 372 374 207 376 288 342 268 210 381 211 383 212 387 388 215 390 216 392 217 396 219 398 220 400 302 222 404 407 408 224 411 412 226 416 417 228 422 230 423 232 425 234 427 235 236 431 433 239 435 240 437 434 242 441 333 444 244 447 245 449 452 247 454 249 456 250 457 386 252 460 255 462 256 305 464 258 467 260 469 262 471 264 474 266 284 476 270 478 272 480 273 458 274 484 276 486 277 488 279 489 280 491 282 494 497 286 499 287 501 459 395 375 291 504 293 506 294 508 295 511 297 513 299 515 300 517 519 521 303 523 410 352 527 306 531 533 308 534 309 538 540 311 542 312 546 430 549 316 551 318 554 320 557 321 560 322 562 324 563 326 565 327 567 329 570 330 572 574 332 576 575 335 580 336 581 453 338 585 340 588 589 343 345 590 347 592 349 594 351 596 598 354 602 356 605 358 607 609 360 413 363 611 365 613 367 369 617 620 371 622 373 389 624 377 626 378 379 630 380 450 634 382 636 384 638 385 640 642 391 439 393 645 394 647 649 397 652 399 654 401 656 402 658 403 660 405 662 406 664 666 668 409 670 672 537 675 477 678 414 680 415 683 473 685 418 686 419 688 420 692 421 694 697 424 700 701 426 704 705 428 709 429 710 712 432 569 715 436 716 438 718 719 440 722 442 724 443 726 445 727 446 729 448 731 732 451 733 735 584 578 455 739 740 742 461 745 463 748 465 750 466 600 753 468 564 758 470 760 763 472 765 766 768 475 552 479 770 481 772 482 582 483 777 780 485 783 487 541 490 785 492 787 493 791 495 496 794 796 498 798 500 800 502 610 503 802 505 507 558 509 806 510 743 808 512 812 514 814 516 816 518 819 520 820 522 822 524 824 525 826 526 829 528 831 529 833 530 835 608 532 838 841 535 843 536 845 691 539 625 849 543 851 544 853 545 856 547 858 548 860 699 863 550 866 868 869 553 873 875 555 876 556 881 882 559 884 885 561 888 889 566 892 893 568 894 896 571 899 573 730 900 577 901 579 902 903 904 583 905 586 720 587 910 912 913 916 811 591 919 920 593 924 595 926 597 928 930 599 932 601 936 759 603 728 604 941 944 606 734 946 947 641 612 948 614 950 615 952 616 618 957 619 959 961 621 725 964 623 706 627 967 628 969 629 973 631 632 977 633 979 635 981 637 713 639 984 643 644 646 659 648 988 650 990 651 993 653 997 655 1000 657 1002 1004 921 661 1006 663 1008 665 767 667 1012 1015 669 1017 671 1019 673 1021 674 676 1025 677 942 1029 679 1031 681 1033 682 781 684 1037 687 934 689 1040 690 1016 1043 693 1045 695 1047 696 1049 1051 698 1052 872 1055 769 1058 702 1060 703 1063 818 1065 1066 707 1068 708 1072 1075 1076 711 1077 1078 1079 714 1083 1084 717 1087 1089 1090 1091 721 1093 1094 723 1097 1098 1099 1100 1101 1102 738 736 737 883 803 972 797 955 1108 741 1110 918 1113 744 1117 1005 746 1118 747 1122 749 1124 751 1127 752 1129 754 1131 755 1133 756 1135 757 1137 1139 761 1143 762 1144 945 764 1147 1148 1150 771 1152 773 1153 774 1155 775 776 1160 778 1162 779 847 782 1165 1168 784 786 1170 788 897 789 1173 790 1176 1177 792 793 1183 795 911 891 1186 799 801 909 804 805 807 1189 809 1191 810 1163 995 1195 813 1130 1200 815 1202 1205 817 1207 1208 987 821 1125 823 1212 825 1214 827 1145 828 1219 1222 830 1224 832 951 834 1226 836 1228 837 1232 839 840 1235 1237 842 1238 844 1240 846 1141 848 1245 850 852 864 854 855 1249 857 1251 859 1253 861 1255 862 1258 1259 865 1261 1003 867 1264 1267 870 1269 871 1271 1071 874 966 1274 877 1276 878 1278 879 1281 880 1283 986 1287 1288 1289 1290 886 1291 887 935 1296 1297 890 1301 1302 985 1305 1306 895 1308 1309 1310 898 1312 1313 1315 1316 1317 1244 906 907 908 1038 1030 1323 914 1325 915 1327 1329 917 1331 1333 1121 1336 922 1338 923 1342 925 1345 1346 927 1209 929 1351 931 1352 933 1354 1355 1285 937 1358 938 1360 939 1362 940 1303 1363 943 1364 1366 1367 1284 1151 949 1020 1371 953 1298 954 1268 1375 956 1378 958 1380 960 962 1088 963 1383 1169 965 1386 968 970 1080 971 1275 1392 1393 974 1395 975 1095 976 1401 978 980 1187 982 983 1404 989 1406 991 992 1409 1411 994 1413 996 1417 1201 998 1361 999 1422 1425 1001 1365 1427 1428 1370 1007 1431 1009 1433 1010 1434 1011 1013 1439 1014 1441 1248 1359 1445 1018 1215 1022 1448 1023 1450 1024 1454 1026 1027 1458 1028 1460 1462 1032 1349 1034 1035 1356 1036 1468 1039 1041 1042 1471 1044 1475 1046 1477 1048 1479 1050 1481 1484 1485 1053 1486 1054 1056 1490 1057 1423 1494 1059 1495 1061 1497 1062 1064 1501 1067 1415 1069 1503 1070 1505 1507 1073 1509 1074 1510 1511 1514 1294 1188 1516 1517 1081 1518 1082 1520 1300 1522 1085 1523 1086 1526 1527 1528 1529 1532 1533 1092 1311 1535 1536 1096 1537 1142 1538 1540 1182 1159 1103 1104 1105 1106 1107 1394 1109 1545 1111 1547 1112 1550 1114 1552 1115 1387 1116 1555 1557 1119 1559 1120 1561 1563 1344 1566 1123 1569 1430 1570 1126 1574 1128 1577 1578 1132 1581 1582 1134 1136 1585 1138 1586 1140 1587 1588 1589 1146 1590 1591 1149 1515 1594 1595 1154 1156 1157 1599 1158 1524 1602 1161 1605 1164 1166 1607 1167 1314 1554 1171 1172 1174 1175 1541 1398 1544 1178 1614 1179 1616 1180 1181 1292 1621 1184 1185 1625 1190 1627 1192 1193 1442 1194 1633 1196 1635 1197 1637 1198 1640 1199 1642 1644 1203 1648 1204 1649 1426 1206 1652 1653 1210 1211 1657 1213 1659 1660 1216 1662 1217 1218 1667 1220 1669 1221 1223 1671 1674 1225 1227 1676 1229 1583 1230 1679 1231 1682 1683 1233 1234 1689 1236 1322 1580 1692 1239 1241 1242 1243 1260 1321 1246 1247 1473 1700 1250 1634 1705 1252 1628 1254 1708 1256 1650 1257 1711 1470 1715 1716 1262 1718 1263 1722 1265 1266 1725 1727 1728 1270 1730 1272 1646 1273 1735 1277 1567 1279 1551 1280 1651 1282 1741 1742 1743 1286 1745 1748 1749 1750 1751 1752 1293 1754 1295 1757 1758 1299 1759 1761 1762 1763 1764 1304 1766 1769 1771 1307 1773 1774 1381 1775 1776 1391 1318 1319 1320 1324 1684 1326 1778 1328 1608 1782 1330 1783 1332 1334 1677 1335 1787 1337 1789 1339 1791 1340 1793 1341 1795 1797 1343 1798 1573 1801 1347 1803 1348 1806 1807 1350 1639 1811 1353 1814 1698 1816 1817 1357 1820 1821 1822 1823 1824 1453 1437 1368 1369 1539 1830 1372 1373 1374 1833 1376 1377 1837 1838 1379 1843 1382 1845 1384 1385 1388 1389 1390 1849 1851 1396 1853 1397 1855 1399 1400 1859 1860 1402 1403 1866 1405 1869 1870 1407 1873 1408 1410 1879 1412 1880 1414 1882 1883 1416 1713 1418 1887 1419 1889 1420 1890 1421 1892 1893 1424 1894 1895 1896 1429 1898 1712 1658 1432 1447 1902 1435 1904 1436 1906 1908 1438 1912 1440 1914 1443 1815 1444 1917 1675 1446 1920 1449 1451 1808 1452 1903 1924 1925 1455 1926 1456 1818 1457 1768 1459 1461 1693 1463 1464 1465 1466 1467 1469 1938 1940 1472 1942 1474 1945 1706 1476 1478 1950 1480 1482 1953 1483 1954 1888 1957 1874 1487 1959 1488 1960 1489 1964 1491 1492 1968 1493 1832 1971 1496 1877 1498 1499 1884 1500 1848 1502 1504 1506 1980 1508 1983 1984 1645 1512 1986 1513 1987 1543 1989 1991 1992 1993 1519 1995 1521 1746 1999 2000 2001 1525 2003 2004 1932 2005 1530 2007 1531 2008 1542 2009 2012 1534 2015 2016 2017 2018 1546 1965 1548 1549 2022 1979 2026 1553 1556 1829 2030 1558 2031 1560 1719 1562 2034 1564 2036 1565 2039 2040 1568 2042 2044 1571 2045 1572 2047 1935 2049 1575 2050 1576 2054 2055 1579 1988 2058 2060 2061 2062 1584 2064 1891 2066 1911 1734 1596 1788 1592 1593 1767 2072 1597 1598 2074 1600 1601 1610 1841 2078 1603 2080 1604 2083 1876 1606 2087 1609 1611 1612 1695 1613 2090 1615 1739 1617 1974 1618 1619 1620 1863 2096 1622 2098 1623 1624 2102 1868 2105 1626 2107 1949 2109 1629 2113 1630 2114 1631 2117 1632 2120 2121 1636 2124 2125 1638 2126 1641 2130 1643 2131 2132 1647 2133 2134 2135 2136 2053 1654 2139 1655 1656 2142 2144 1661 1812 1663 1802 1664 2147 1665 2149 1666 2152 1668 2155 1670 1672 2158 1673 2065 2028 1678 1680 1681 1929 2019 2164 1685 2166 1686 1687 2051 1688 1690 1691 1694 1696 1697 2175 1699 2177 1701 2178 1702 1703 2182 1704 2184 2186 1707 2189 1709 1710 2193 2194 1714 2196 2199 1717 2201 2128 1720 2203 1721 2206 2207 1723 1724 2212 1726 2123 2215 1729 1731 1732 1733 2041 1736 1737 1738 2222 2223 1740 2226 2063 1744 2228 2229 1747 2230 2231 1847 2233 1867 1753 2235 1755 1756 1990 2073 2239 2240 1760 2242 2243 1948 1765 2245 2246 1941 1770 2248 2013 1772 2252 1836 2253 2251 2254 1777 1779 1780 2071 1781 2257 1828 2260 1784 1785 1786 2263 2264 1790 1792 2267 1794 2269 1796 2159 2221 2273 1799 2274 1800 2277 2278 1804 2279 1805 2281 2282 1809 2283 1810 2057 2285 2286 1813 2232 2288 2291 2292 2293 1819 2156 2294 2089 1825 1826 2296 1827 2014 2067 1831 2300 1834 1835 1921 2303 1839 2069 1840 2202 1852 1842 2307 1844 2311 1846 1850 2313 1854 1856 1857 1858 1936 2318 1861 1981 1862 2218 1864 2323 1865 2325 2327 2328 2112 2023 2332 1871 2334 1872 2200 2337 1875 2339 2341 2342 1878 2181 2346 1881 2349 2220 2351 2352 1885 2354 1886 2357 2358 2359 2360 2361 2225 1963 2362 1897 2295 1899 1900 2367 1901 2370 1905 1907 2373 1909 2056 1910 2046 2377 2378 1913 2345 1915 1916 2384 1918 1919 1922 1923 2075 2389 1927 2390 1928 2374 1930 1931 2395 1933 1934 1937 2024 1939 2402 2403 1943 2405 1944 2407 1946 2409 1947 2410 2411 2413 2190 1951 2416 1952 2419 2420 1955 2350 1956 2423 2174 1958 2426 1961 2343 1962 2428 2430 2431 2432 1966 2355 1967 2439 1969 1970 2216 1972 1973 1975 1976 1977 1978 2444 2180 2445 1982 2298 1985 2447 2448 2449 2450 2451 2453 1994 2455 1996 1997 1998 2459 2400 2002 2101 2086 2006 2463 2398 2010 2465 2011 2466 2468 2469 2471 2472 2020 2021 2476 2025 2238 2480 2027 2029 2068 2483 2032 2033 2137 2035 2486 2037 2038 2489 2491 2079 2043 2369 2494 2495 2379 2048 2497 2347 2333 2052 2499 2500 2501 2185 2059 2503 2317 2505 2506 2467 2507 2508 2509 2070 2249 2512 2076 2077 2515 2081 2082 2084 2165 2085 2297 2091 2475 2088 2306 2092 2093 2094 2095 2525 2097 2099 2100 2224 2530 2103 2532 2104 2535 2536 2106 2526 2108 2540 2110 2541 2111 2543 2545 2115 2433 2116 2442 2547 2118 2548 2119 2551 2552 2122 2424 2555 2557 2558 2127 2560 2561 2129 2563 2227 2524 2438 2418 2565 2566 2138 2140 2141 2572 2143 2504 2387 2145 2146 2575 2148 2150 2151 2381 2579 2153 2580 2154 2287 2157 2585 2160 2161 2162 2163 2588 2191 2167 2168 2169 2170 2592 2171 2594 2172 2173 2597 2176 2600 2601 2179 2603 2604 2605 2183 2607 2608 2609 2187 2272 2188 2612 2614 2615 2192 2617 2562 2195 2197 2620 2198 2564 2266 2204 2338 2205 2435 2473 2624 2208 2625 2209 2210 2549 2211 2631 2213 2214 2217 2219 2636 2329 2406 2638 2596 2639 2640 2641 2642 2316 2234 2646 2236 2237 2452 2513 2241 2652 2244 2653 2247 2644 2654 2250 2655 2656 2657 2315 2364 2255 2659 2256 2662 2258 2259 2664 2481 2261 2262 2484 2265 2268 2667 2270 2271 2573 2368 2672 2275 2276 2372 2674 2280 2587 2284 2679 2680 2681 2289 2643 2290 2514 2684 2658 2685 2686 2299 2470 2388 2301 2302 2492 2304 2305 2308 2309 2310 2391 2461 2312 2314 2694 2319 2320 2321 2322 2692 2324 2699 2326 2701 2454 2704 2330 2331 2478 2710 2632 2335 2593 2336 2712 2340 2713 2714 2344 2715 2554 2717 2718 2348 2720 2721 2696 2724 2353 2726 2727 2356 2618 2728 2485 2648 2363 2628 2365 2733 2366 2736 2683 2371 2738 2375 2376 2516 2742 2570 2380 2743 2382 2383 2748 2385 2386 2750 2392 2393 2394 2754 2396 2417 2397 2399 2757 2758 2401 2464 2761 2404 2763 2764 2765 2408 2768 2462 2511 2412 2414 2771 2415 2772 2553 2542 2735 2421 2422 2775 2425 2427 2429 2779 2780 2434 2781 2436 2437 2546 2785 2786 2440 2441 2443 2520 2446 2792 2663 2793 2747 2794 2795 2796 2797 2647 2456 2766 2457 2458 2460 2803 2666 2804 2523 2805 2806 2807 2808 2474 2626 2811 2477 2791 2479 2482 2813 2487 2488 2490 2818 2790 2493 2822 2496 2824 2498 2676 2574 2826 2827 2502 2829 2830 2831 2598 2510 2517 2518 2519 2521 2522 2637 2705 2527 2528 2529 2531 2839 2533 2665 2534 2842 2844 2537 2845 2538 2539 2801 2825 2544 2850 2851 2731 2729 2550 2854 2855 2856 2857 2613 2556 2859 2860 2559 2833 2862 2863 2567 2568 2865 2569 2868 2869 2571 2870 2798 2751 2576 2577 2578 2823 2581 2582 2583 2734 2584 2816 2586 2689 2589 2590 2591 2881 2595 2616 2802 2884 2885 2599 2888 2602 2837 2891 2892 2893 2606 2895 2610 2611 2872 2898 2719 2619 2901 2621 2622 2623 2904 2815 2809 2627 2629 2630 2788 2908 2909 2633 2634 2635 2912 2649 2913 2820 2914 2915 2703 2645 2916 2886 2650 2651 2698 2879 2707 2917 2867 2918 2660 2661 2760 2800 2814 2668 2922 2669 2670 2678 2671 2925 2673 2740 2675 2723 2677 2928 2706 2682 2930 2880 2874 2687 2688 2690 2691 2693 2695 2697 2929 2700 2702 2939 2902 2936 2942 2910 2708 2709 2711 2778 2903 2716 2819 2753 2949 2950 2951 2722 2948 2953 2725 2955 2799 2730 2956 2957 2732 2959 2943 2960 2737 2931 2739 2741 2744 2745 2746 2864 2749 2752 2945 2755 2756 2967 2968 2759 2969 2889 2762 2972 2973 2894 2974 2767 2828 2769 2770 2835 2773 2774 2789 2776 2777 2907 2782 2783 2784 2982 2923 2787 2919 2984 2847 2985 2986 2987 2975 2988 2810 2812 2871 2990 2958 2817 2978 2821 2853 2873 2971 2977 2992 2890 2832 2834 2836 2838 2840 2841 2932 2843 2952 2997 2846 2848 2849 2991 2852 2946 2999 2920 2979 2858 2954 2861 2963 2976 2877 2866 3001 2924 2875 2876 2878 2899 2882 2883 2993 2964 2935 2887 2994 2989 2970 2947 2896 2981 2897 2998 2900 2905 2906 2966 2911 3000 2926 2933 2996 3002 2921 3003 2927 2941 2934 2937 2938 2940 2962 2944 2965 2995 2961 2980 2983