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