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