248956422 242193529 198295559 190214555 181538259 170805979 159345973 145138636 138394717 133797422 135086622 133275309 114364328 107043718 101991189 90338345 83257441 80373285 58617616 64444167 46709983 50818468 156040895 57227415 16569 175055 32032 127682 66860 40176 42210 176043 40745 41717 161471 153799 155397 209709 92689 40062 38054 176845 39050 100316 201709 211173 194050 191469 38115 39555 172810 43739 448248 1872759 185591 280839 112551 150754 41543 179772 165050 42811 181920 103838 99375 73985 37240 2274 2165 1942 1472 21476 4416 1201 1444 2276 998 12399 37690 1179 2646 2489 1029 2145 2321 2140 2043 1445 981 1884 1361 392061 1233 1774 3920 92983 112505 4055 2415 2318 2186 1951 1300 22689 138126 5674 8127 6361 5353 3253 1899 2983 2168 993 91309 1202 1599 1400 2969 1553 7046 31033 44474 4685 4513 6504 6158 3041 5796 1652 1040 1368 2699 1048 1428 1428 1026 1121 1803 2855 3530 8320 1048 1045 1298 2387 1537 1143 1880 1216 970 1788 1484 1750 1308 1658 971 1930 990 4215 1136 2656 1650 1451 2378 2805 7992 7642 182896 179198 161802 179693 157432 15008 164239 210658 168472 41891 66486 198735 93321 158759 148850 150742 27745 62944 40191 36723 79590 71251 137718 186739 176608 161147 171823 2200 3033 3112 1642 1393 1103 1039 1619 3122 1934 3111 2545 2295 1551 2046 1222 1535 3784 1329 1238 5623 5821 2960 1848 2315 1945 1424 1274 1007 1414 1725 5354 2189 1294 1831 1647 2943 2857 1030 1070 1735 1982 1564 1775 1540 2013 1176 1890 3644 2785 1017 1068 1007 2605 8410 5534 2173 1065 8683 2670 2420 2189 2093 1184 1205 2786 2794 19544 2848 10556 9066 7267 2462 1774 1297 4379 4208 4068 2940 3938 2072 1136 4248 5823 3715 4885 4813 2899 1228 3119 3828 1186 1908 2795 3703 6722 6466 2235 2871 4632 4225 4339 2305 3273 5701 4154 1243 1308 2922 3044 2888 1742 4969 3270 6028 1105 2884 1124 1454 2565 2149 2630 14625 7431 5776 4820 1227 7503 9652 1091 2467 1270 4365 4284 10282 5601 4758 1624 4024 1276 5083 2075 3553 7010 4718 3546 2873 2144 2243 5343 4877 3034 2826 1221 1169 2319 3450 2674 3912 6020 2303 2552 3656 1591 1209 3176 8915 4902 3324 5997 2618 10311 2440 12444 5691 2717 5277 4373 3224 2631 5385 3678 1412 1443 1098 3240 1915 4667 7219 3277 3473 4243 17599 5095 2237 2901 2666 5336 4383 5446 6252 4616 3021 3667 4563 1120 3845 2272 4764 5410 7150 1762 1207 1331 8307 2276 2575 3970 1352 3040 2070 2913 2389 1835 4807 2201 1265 1961 1064 1932 3213 1178 2926 1038 3298 8992 6698 4880 1766 3532 2297 1234 1205 2790 2006 4593 1579 9597 10451 3219 2300 5985 2959 1340 3148 2242 16513 7821 2159 2114 4109 1544 1005 8632 1012 4728 2165 7591 5202 4241 4131 2272 2085 4346 1208 4543 2772 2490 4568 1776 2699 3534 2424 1747 1088 1143 2530 8049 1366 4284 33125 2137 3840 3087 2041 3344 2921 6581 3968 2339 1243 7776 19837 1737 1098 1893 1281 1527 2055 2527 3275 1265 2623 4850 3584 2561 3041 1409 4596 11555 1266 1079 1087 1226 1131 1199 1084 2038 1070 1312 4031 7445 1770 5600 1882 1170 1300 5325 2043 1072 2463 1010 1432 1162 1095 1118 1383 2289 1648 2203 3270 11499 2474 2294 1238 3410 1523 62955 6282 3836 6486 15368 9572 6413 4104 12943 4650 3080 3134 6211 1126 1101 1101 2648 2973 2520 2318 2606 2205 2929 3869 1117 2960 1009 4048 2193 1830 25139 18532 15240 13739 11297 10074 9891 9774 9727 9358 8920 8479 8312 8261 8131 8051 7832 7710 7702 7479 7368 7162 7065 7019 6997 6994 6979 6797 6525 6246 5926 5914 5898 5879 5834 5743 5577 5413 5250 5246 5118 5058 4959 4853 4828 4819 4809 4710 4680 4645 4514 4439 4416 4409 4392 4359 4319 4290 4242 4228 4222 4216 4210 4206 4102 4101 4083 3967 3955 3945 3930 3929 3924 3919 3908 3892 3890 3859 3846 3835 3830 3828 3825 3821 3809 3801 3799 3737 3701 3698 3692 3686 3677 3664 3613 3611 3606 3584 3581 3543 3528 3527 3496 3493 3484 3435 3391 3374 3371 3361 3351 3340 3320 3282 3278 3260 3258 3253 3247 3230 3224 3216 3212 3194 3189 3177 3176 3173 3170 3166 3163 3143 3137 3116 3106 3093 3079 3053 3051 3015 3012 3009 2997 2997 2983 2979 2967 2967 2966 2954 2952 2934 2918 2895 2887 2879 2878 2872 2868 2866 2865 2864 2859 2854 2830 2828 2824 2819 2813 2809 2802 2791 2783 2778 2777 2770 2769 2767 2763 2745 2742 2736 2729 2726 2719 2715 2708 2704 2692 2691 2690 2687 2677 2668 2668 2663 2655 2644 2642 2632 2632 2628 2623 2622 2619 2605 2603 2601 2598 2597 2596 2594 2586 2585 2583 2578 2569 2569 2551 2548 2548 2546 2545 2534 2533 2522 2522 2515 2513 2507 2504 2497 2471 2465 2464 2459 2457 2450 2435 2434 2432 2427 2421 2420 2414 2404 2403 2402 2397 2395 2394 2388 2382 2381 2380 2368 2364 2363 2348 2339 2335 2332 2331 2330 2323 2319 2314 2308 2306 2296 2287 2279 2276 2273 2262 2254 2252 2245 2239 2223 2220 2218 2215 2213 2203 2200 2197 2194 2183 2179 2177 2177 2177 2168 2160 2155 2144 2143 2136 2134 2129 2128 2125 2125 2122 2111 2106 2094 2093 2088 2086 2086 2084 2080 2079 2076 2071 2066 2061 2055 2053 2040 2036 2035 2034 2032 2029 2025 2021 2018 2015 2009 2007 2005 2003 2001 2001 2000 1996 1992 1985 1981 1977 1971 1968 1962 1961 1960 1960 1954 1952 1947 1944 1943 1941 1937 1934 1929 1924 1924 1923 1921 1918 1915 1915 1914 1912 1910 1907 1904 1897 1891 1890 1888 1888 1885 1881 1879 1877 1876 1876 1874 1872 1869 1866 1865 1865 1865 1862 1862 1859 1856 1856 1854 1850 1849 1849 1847 1839 1834 1821 1815 1811 1808 1808 1807 1807 1802 1801 1800 1795 1794 1792 1788 1786 1782 1782 1781 1781 1779 1777 1764 1762 1755 1749 1747 1746 1745 1744 1742 1740 1740 1736 1735 1732 1732 1730 1727 1722 1718 1716 1710 1708 1707 1706 1705 1704 1699 1698 1697 1697 1695 1695 1693 1687 1686 1680 1679 1679 1678 1674 1674 1671 1669 1665 1663 1657 1653 1652 1650 1649 1649 1640 1638 1636 1632 1631 1630 1627 1624 1617 1616 1615 1611 1611 1606 1605 1605 1600 1598 1598 1597 1596 1595 1592 1589 1585 1579 1578 1577 1577 1577 1576 1575 1574 1572 1571 1563 1561 1561 1560 1560 1554 1552 1548 1546 1541 1536 1533 1532 1532 1530 1527 1526 1524 1523 1523 1522 1522 1519 1513 1508 1508 1505 1503 1496 1491 1490 1490 1487 1486 1485 1484 1483 1479 1479 1476 1475 1472 1469 1468 1467 1465 1464 1463 1463 1459 1459 1458 1458 1454 1449 1449 1448 1446 1442 1441 1440 1439 1437 1436 1429 1429 1427 1426 1425 1424 1424 1423 1423 1423 1414 1414 1413 1413 1410 1409 1409 1406 1405 1405 1404 1404 1402 1402 1402 1402 1400 1398 1396 1395 1394 1393 1391 1389 1389 1388 1387 1384 1381 1381 1379 1377 1376 1376 1375 1374 1372 1371 1370 1370 1366 1363 1360 1356 1355 1355 1352 1345 1344 1344 1342 1342 1336 1334 1334 1333 1332 1328 1328 1328 1327 1325 1322 1320 1319 1318 1315 1314 1313 1313 1312 1310 1309 1309 1307 1307 1305 1304 1303 1302 1302 1301 1301 1300 1299 1297 1295 1294 1293 1291 1291 1289 1288 1288 1287 1287 1287 1286 1283 1281 1277 1274 1270 1267 1266 1260 1259 1258 1258 1258 1256 1255 1254 1254 1253 1250 1249 1248 1248 1247 1242 1242 1241 1241 1241 1239 1238 1237 1236 1235 1234 1234 1234 1233 1232 1232 1231 1230 1228 1227 1227 1226 1224 1224 1220 1220 1219 1217 1216 1215 1214 1214 1214 1213 1212 1209 1208 1207 1207 1207 1206 1206 1205 1205 1204 1204 1204 1203 1201 1201 1200 1200 1199 1198 1197 1196 1195 1194 1194 1191 1189 1186 1186 1184 1183 1183 1182 1181 1181 1181 1181 1179 1178 1178 1177 1177 1171 1171 1171 1170 1170 1167 1167 1167 1165 1165 1162 1157 1156 1156 1154 1154 1151 1151 1150 1150 1147 1147 1146 1144 1144 1143 1142 1141 1141 1140 1138 1134 1134 1132 1131 1131 1130 1127 1126 1124 1122 1122 1121 1119 1119 1119 1119 1118 1116 1116 1115 1115 1115 1114 1113 1113 1110 1110 1109 1108 1107 1107 1107 1107 1106 1103 1103 1103 1100 1099 1098 1097 1096 1096 1094 1093 1090 1088 1087 1086 1085 1084 1084 1084 1084 1083 1083 1082 1082 1081 1081 1079 1076 1074 1073 1073 1071 1069 1067 1067 1067 1066 1065 1065 1065 1065 1065 1064 1064 1064 1063 1062 1062 1062 1061 1060 1057 1057 1056 1055 1055 1055 1055 1054 1051 1050 1050 1049 1048 1047 1046 1046 1046 1045 1045 1045 1044 1042 1041 1039 1039 1038 1036 1036 1035 1035 1033 1032 1031 1031 1031 1027 1027 1026 1026 1024 1024 1022 1022 1021 1020 1019 1018 1018 1018 1016 1010 1010 1009 1008 1007 1006 1005 1005 1004 1004 1003 1003 1003 1003 1002 1002 1000 1000 8358 7932 6846 4591 4041 3841 3754 3743 3702 3625 3529 3508 3359 3320 3231 3220 3212 3192 3092 3087 3048 3005 3004 2959 2934 2933 2827 2794 2749 2745 2733 2698 2665 2634 2492 2489 2468 2414 2395 2356 2339 2310 2288 2285 2269 2253 2203 2176 2159 2155 2149 2129 2116 2113 2098 2066 2066 2059 2047 2040 2030 2024 2001 1992 1981 1979 1957 1953 1944 1936 1932 1882 1878 1870 1821 1813 1809 1804 1797 1791 1781 1766 1764 1743 1741 1709 1706 1701 1689 1646 1641 1639 1636 1632 1629 1623 1622 1622 1619 1606 1593 1592 1558 1545 1542 1540 1529 1518 1515 1513 1507 1504 1499 1495 1495 1492 1492 1489 1485 1483 1473 1470 1463 1460 1458 1456 1453 1443 1441 1426 1425 1418 1413 1413 1412 1407 1406 1396 1390 1382 1376 1375 1371 1367 1364 1356 1355 1352 1350 1346 1345 1340 1330 1329 1324 1316 1307 1304 1304 1303 1301 1300 1297 1296 1290 1284 1282 1281 1280 1279 1272 1267 1267 1266 1264 1264 1264 1263 1249 1240 1239 1235 1235 1233 1232 1230 1226 1223 1214 1213 1211 1209 1202 1199 1197 1193 1191 1187 1186 1184 1184 1182 1179 1173 1169 1167 1166 1165 1164 1163 1158 1158 1157 1157 1157 1155 1154 1149 1148 1148 1146 1144 1140 1136 1134 1133 1129 1127 1127 1118 1110 1104 1104 1101 1098 1096 1094 1091 1089 1086 1085 1084 1083 1083 1079 1076 1069 1068 1067 1067 1067 1063 1062 1059 1058 1058 1055 1054 1054 1053 1053 1052 1051 1049 1047 1044 1043 1043 1042 1042 1041 1040 1039 1038 1037 1037 1035 1027 1021 1021 1019 1019 1016 1014 1013 1009 1008 1007 1004 1004 1003 1001 1000 1000 1000 17929 9749 8053 7826 7768 5691 5444 5077 4990 4545 4544 4202 4195 3807 3741 3699 3640 3531 3455 3411 3387 3358 3285 3273 3262 3259 3222 3127 3110 3104 3071 3063 3059 2990 2986 2928 2922 2875 2859 2850 2813 2785 2736 2688 2658 2643 2618 2605 2583 2534 2512 2500 2481 2478 2473 2467 2442 2430 2417 2408 2395 2352 2337 2322 2307 2306 2292 2271 2265 2260 2240 2238 2228 2215 2205 2191 2191 2190 2184 2166 2165 2162 2146 2116 2112 2108 2106 2106 2106 2097 2081 2058 2055 2054 2037 2032 2032 2020 2018 2014 2001 2001 1991 1990 1983 1981 1981 1979 1963 1932 1929 1881 1874 1849 1849 1833 1832 1826 1814 1814 1791 1789 1786 1778 1776 1762 1758 1757 1754 1752 1751 1749 1738 1729 1726 1716 1712 1711 1703 1702 1699 1686 1684 1680 1678 1678 1677 1676 1672 1669 1668 1663 1660 1660 1658 1656 1656 1652 1647 1645 1641 1638 1633 1626 1614 1612 1605 1603 1599 1589 1588 1585 1584 1584 1580 1572 1570 1569 1568 1567 1565 1559 1559 1556 1554 1549 1542 1541 1538 1537 1535 1530 1528 1522 1514 1509 1507 1500 1499 1499 1497 1496 1488 1486 1485 1481 1479 1472 1472 1470 1466 1465 1461 1458 1457 1448 1447 1444 1443 1443 1438 1432 1430 1430 1429 1429 1429 1426 1426 1420 1416 1416 1415 1415 1414 1413 1410 1405 1402 1398 1397 1395 1392 1388 1386 1382 1381 1379 1376 1374 1374 1373 1373 1372 1370 1367 1365 1364 1361 1361 1355 1355 1354 1353 1349 1345 1344 1343 1338 1338 1338 1336 1333 1333 1332 1324 1323 1323 1320 1320 1317 1316 1304 1304 1303 1302 1301 1300 1298 1297 1295 1284 1283 1283 1279 1278 1271 1271 1268 1264 1263 1262 1261 1260 1259 1259 1258 1256 1253 1248 1248 1246 1246 1244 1238 1238 1236 1234 1234 1231 1231 1230 1230 1228 1227 1222 1222 1221 1221 1220 1218 1218 1216 1216 1212 1210 1209 1208 1208 1206 1205 1205 1202 1200 1199 1198 1198 1198 1195 1194 1191 1189 1188 1180 1180 1179 1172 1168 1166 1157 1156 1156 1155 1154 1154 1149 1143 1143 1140 1137 1135 1135 1135 1127 1127 1126 1123 1123 1123 1122 1122 1121 1121 1119 1119 1119 1118 1115 1106 1106 1104 1102 1101 1098 1098 1096 1096 1095 1093 1090 1089 1087 1087 1085 1085 1085 1083 1080 1080 1079 1079 1079 1075 1074 1073 1070 1068 1067 1066 1066 1066 1063 1063 1063 1062 1058 1056 1052 1051 1051 1050 1048 1046 1046 1045 1043 1038 1036 1035 1035 1035 1033 1032 1031 1026 1026 1026 1023 1022 1020 1020 1020 1019 1018 1018 1017 1015 1015 1015 1014 1014 1013 1013 1013 1012 1011 1011 1009 1008 1008 1007 1007 1007 1006 1005 1003 1001 1000 19311 11713 11263 9779 9568 9344 9188 9100 8771 8690 8566 8058 7759 7585 7471 7461 7342 7223 7064 6916 6897 6880 6857 6840 6728 6688 6553 6396 6345 6295 6266 6173 6171 6120 6105 6099 5893 5829 5793 5776 5759 5716 5708 5590 5566 5558 5418 5375 5300 5255 5157 5130 4978 4957 4947 4897 4867 4845 4678 4641 4592 4543 4532 4503 4495 4444 4414 4409 4302 4300 4277 4173 4169 4136 4101 4089 4015 4000 3973 3732 3709 3686 3676 3673 3672 3633 3633 3613 3605 3592 3586 3584 3577 3537 3510 3509 3488 3473 3445 3427 3395 3367 3337 3324 3315 3313 3283 3250 3247 3237 3235 3200 3195 3175 3158 3143 3139 3138 3136 3132 3132 3095 3094 3093 3059 2985 2975 2967 2961 2955 2935 2933 2909 2904 2892 2886 2885 2878 2875 2861 2856 2838 2801 2797 2788 2773 2755 2754 2743 2725 2722 2682 2669 2663 2652 2647 2635 2633 2629 2612 2599 2566 2556 2551 2551 2538 2538 2525 2498 2496 2483 2475 2469 2455 2444 2437 2435 2427 2419 2413 2412 2400 2399 2396 2393 2386 2384 2382 2382 2367 2366 2362 2361 2353 2349 2348 2340 2339 2336 2333 2330 2327 2318 2293 2292 2287 2274 2274 2267 2260 2257 2240 2239 2232 2230 2230 2222 2216 2214 2210 2203 2197 2196 2196 2179 2178 2178 2172 2170 2167 2167 2157 2153 2151 2147 2145 2142 2142 2136 2130 2128 2126 2126 2119 2107 2091 2087 2086 2083 2075 2075 2072 2068 2067 2055 2051 2050 2033 2024 2016 2011 2009 2003 2001