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