#include <bits/stdc++.h>
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/12/15  Problem: world_codesprint12 C / Link: __CONTEST_URL__  ----- */


int memo[10001] = { 0,0,1,1,3,1,4,1,7,4,6,1,10,1,8,6,15,1,13,1,16,8,12,1,22,6,14,13,22,1,21,1,31,12,18,8,31,1,20,14,36,1,29,1,34,21,24,1,46,8,31,18,40,1,40,12,50,20,30,1,51,1,32,29,63,14,45,1,52,24,43,1,67,1,38,31,58,12,53,1,76,40,42,1,71,18,44,30,78,1,66,14,70,32,48,20,94,1,57,45,81,1,69,1,92,43,54,1,94,1,67,38,106,1,77,24,88,53,60,18,111,12,62,42,94,31,92,1,127,44,79,1,111,20,68,66,120,1,93,1,113,48,72,14,139,30,74,57,112,1,106,1,134,69,89,32,131,1,80,54,156,24,121,1,124,67,84,1,155,14,103,77,130,1,117,43,166,60,90,1,156,1,105,62,162,38,125,18,142,92,115,1,190,1,98,79,155,1,144,1,181,68,102,30,171,42,104,93,196,20,148,1,160,72,108,44,202,32,110,74,177,18,149,1,218,106,114,1,191,1,139,89,204,1,170,48,178,80,137,1,231,1,133,121,184,57,165,20,218,84,156,1,218,24,128,103,255,1,173,38,209,117,132,1,243,54,153,90,202,1,201,1,256,105,138,67,231,1,140,125,253,1,189,1,214,115,157,42,283,18,175,98,220,1,204,60,260,144,150,24,256,44,152,102,286,62,222,1,243,104,187,1,287,1,158,148,238,1,213,30,316,108,185,20,283,79,164,110,288,48,232,1,250,149,168,68,323,1,183,114,273,32,248,57,302,139,174,1,291,1,218,170,342,1,237,72,268,137,180,1,336,20,182,133,287,74,245,1,346,165,223,54,311,1,205,156,330,30,281,1,305,128,192,1,382,89,194,173,292,1,274,24,351,132,198,80,342,1,200,153,381,1,269,32,304,201,233,38,375,1,247,138,310,60,300,84,404,140,229,1,358,1,212,189,372,103,285,62,322,157,259,1,418,1,249,175,328,24,293,1,397,204,239,1,371,90,224,150,442,1,331,42,340,152,228,105,419,1,230,222,369,1,320,1,436,187,234,1,404,68,283,158,414,44,317,115,375,213,240,1,471,38,242,185,375,98,364,1,428,164,302,1,411,30,267,232,466,72,333,1,406,168,252,1,470,102,277,183,382,1,358,74,511,248,258,104,431,48,297,174,469,1,378,1,394,218,264,32,507,24,319,237,419,42,357,108,470,180,270,89,471,1,272,182,528,110,378,1,412,245,342,30,507,80,278,223,418,1,404,44,533,205,282,1,471,114,284,281,498,1,400,1,443,192,329,139,571,1,307,194,465,84,389,54,512,274,294,1,498,32,355,198,556,1,441,137,448,200,323,1,556,1,345,269,454,133,405,1,590,233,367,48,528,1,308,247,551,1,413,1,497,300,312,90,599,156,314,229,472,38,463,1,554,212,318,128,531,105,349,285,636,1,429,1,507,259,343,1,607,60,404,249,490,1,437,132,616,293,377,1,562,1,332,239,582,153,482,30,502,224,403,62,659,1,338,331,521,1,453,98,613,228,373,1,590,138,400,230,646,54,484,1,520,320,348,140,639,42,350,234,568,1,521,38,694,283,354,102,591,1,427,317,624,32,494,157,538,240,360,1,696,104,381,242,544,175,496,1,651,364,439,44,611,1,368,302,714,68,534,1,593,267,425,1,683,150,374,333,579,108,531,1,706,252,407,152,659,1,380,277,685,1,509,110,574,358,384,60,766,1,474,258,580,1,560,187,680,297,390,42,664,72,415,378,743,158,525,1,592,264,475,114,738,62,398,319,598,1,552,48,781,357,402,74,671,185,435,270,708,1,606,1,639,272,445,164,783,44,410,378,657,1,549,1,722,342,473,1,714,1,499,278,820,137,557,168,647,404,420,1,778,30,422,282,634,183,612,133,796,284,528,38,711,1,489,400,750,1,586,1,689,329,432,1,850,174,434,307,683,80,610,68,764,389,461,218,731,1,440,294,837,1,645,1,681,355,444,1,815,128,535,441,670,48,597,180,890,323,450,32,781,54,493,345,792,182,605,1,682,405,560,1,875,84,458,367,688,132,681,1,829,308,462,72,782,223,464,413,900,1,652,153,700,312,468,205,872,1,537,314,753,1,629,42,886,463,517,1,791,74,590,318,851,1,690,192,718,349,480,138,951,32,519,429,724,194,668,1,859,343,583,1,850,140,488,404,916,1,653,90,792,437,492,1,903,198,523,377,761,44,727,1,962,332,569,200,831,1,500,482,906,157,669,60,754,403,504,54,974,1,607,338,783,1,690,233,890,453,510,1,868,1,585,373,1023,247,761,80,772,400,619,1,947,1,565,484,815,62,693,1,989,348,522,150,900,229,524,350,918,1,743,1,790,521,559,212,1035,152,553,354,849,1,768,1,951,427,575,98,891,1,643,494,1006,38,717,259,808,360,628,84,1011,48,542,381,814,249,725,1,1072,496,655,1,924,1,548,439,960,1,794,158,892,368,581,1,1059,239,633,534,832,1,778,102,974,425,558,224,962,1,603,374,1093,60,766,1,844,531,564,185,1035,1,679,407,850,104,848,228,1066,380,570,68,970,164,572,509,1015,230,765,38,903,384,714,1,1147,1,578,474,885,90,773,62,1045,560,665,1,971,234,637,390,1096,168,859,1,880,415,588,283,1086,108,621,525,945,1,789,183,1148,475,594,1,1035,42,732,398,1044,1,797,240,921,552,600,110,1156,1,602,402,947,242,872,72,1058,435,738,174,1011,1,608,606,1198,1,842,54,977,445,659,1,1140,302,614,410,922,1,862,1,1167,549,618,267,1031,1,620,473,1117,74,921,114,934,499,713,44,1223,1,781,557,940,180,856,252,1100,420,667,1,1093,98,632,422,1186,277,845,182,952,612,763,42,1167,68,742,528,987,1,924,1,1276,489,642,1,1071,258,644,586,1151,1,904,1,989,432,648,297,1255,1,709,434,1054,1,900,1,1142,610,654,1,1091,205,787,461,1272,102,950,264,1035,440,660,1,1222,1,662,645,994,319,902,1,1246,444,818,133,1148,44,697,535,1170,192,893,104,1073,597,733,80,1331,270,674,450,1012,72,1006,194,1197,493,678,272,1131,60,777,605,1293,1,909,48,1055,560,684,1,1274,38,823,458,1086,1,917,342,1334,681,743,198,1174,1,692,462,1212,278,1013,74,1042,464,835,108,1335,200,739,652,1048,128,933,1,1268,468,702,62,1223,282,741,537,1398,1,988,84,1060,629,809,284,1299,110,710,517,1137,233,1028,1,1336,590,745,1,1208,1,872,690,1254,1,957,329,1078,480,720,1,1416,132,825,519,1103,307,965,1,1268,668,900,1,1222,1,728,583,1379,48,1093,1,1169,488,775,229,1343,294,734,653,1102,114,1037,1,1450,492,805,355,1272,212,740,523,1333,1,1008,1,1167,727,744,1,1427,1,895,569,1120,1,1080,323,1327,500,857,1,1281,80,752,669,1458,345,1005,138,1161,504,907,1,1415,90,758,607,1138,42,1036,249,1445,690,762,1,1271,367,873,510,1338,140,1123,1,1150,585,827,308,1534,54,770,761,1244,68,1029,1,1352,619,774,239,1334,1,962,565,1456,1,1074,312,1168,693,821,1,1444,224,853,522,1197,314,1161,1,1527,524,943,1,1311,157,788,743,1380,84,1053,1,1265,559,905,1,1530,318,855,553,1192,228,1114,44,1394,768,798,349,1350,1,847,575,1581,1,1158,230,1204,643,877,1,1475,1,990,717,1241,1,1077,343,1516,628,810,1,1416,1,812,542,1451,404,1085,1,1259,725,979,234,1599,72,861,655,1228,1,1197,150,1477,548,822,54,1371,377,824,794,1546,98,1167,128,1299,581,828,332,1542,1,830,633,1329,152,1109,1,1652,778,970,1,1391,1,1003,558,1483,240,1241,403,1258,603,840,74,1618,42,871,766,1264,338,1125,242,1478,564,1028,90,1458,1,980,679,1644,1,1133,1,1378,848,889,132,1563,373,854,570,1343,1,1255,60,1606,572,858,400,1444,102,860,765,1549,1,1190,1,1294,714,864,158,1714,267,1039,578,1300,1,1174,348,1551,773,949,48,1480,1,939,665,1636,350,1262,1,1335,637,1093,104,1607,1,878,859,1318,252,1173,1,1717,588,882,44,1527,354,884,621,1565,62,1240,277,1330,789,888,427,1703,1,1017,594,1425,138,1332,1,1562,732,941,1,1491,1,1075,797,1786,164,1220,360,1348,600,931,258,1681,1,955,602,1395,381,1248,140,1696,872,1087,1,1511,297,908,738,1590,80,1314,108,1470,608,912,1,1787,439,997,842,1372,60,1282,1,1604,659,1049,368,1599,168,920,614,1749,264,1229,98,1384,862,995,1,1706,44,1148,618,1390,110,1340,425,1828,620,930,183,1582,1,1084,921,1632,374,1245,1,1402,713,1140,1,1808,1,938,781,1475,1,1253,1,1693,856,942,270,1571,407,985,667,1830,1,1408,62,1463,632,948,380,1739,272,1023,845,1540,1,1269,174,1803,763,954,1,1644,84,1147,742,1674,1,1306,384,1438,924,1097,102,1911,114,993,642,1481,474,1392,48,1688,644,1159,1,1634,1,968,904,1827,150,1312,278,1553,648,972,68,1822,390,1113,709,1462,1,1379,1,1892,900,978,415,1631,104,1069,654,1772,54,1418,152,1474,787,984,282,1887,180,1183,950,1509,1,1364,475,1749,660,1033,1,1717,284,992,662,1954,398,1325,1,1563,902,1195,182,1827,1,998,818,1498,1,1481,1,1906,697,1158,1,1671,402,1063,893,1758,329,1408,1,1510,733,1061,435,1982,1,1010,674,1617,48,1349,307,1795,1006,1014,1,1704,1,1248,678,1906,108,1470,445,1528,777,1020,1,1888,158,1022,909,1607,410,1396,90,2047,684,1272,294,1787,1,1107,823,1800,205,1429,72,1649,917,1032,1,1979,473,1034,743,1599,1,1519,110,1851,692,1099,499,1731,68,1040,1013,2029,1,1389,1,1564,835,1193,1,1944,1,1274,739,1570,323,1397,420,1966,933,1050,1,1793,192,1052,702,1842,422,1574,345,1613,741,1267,1,2091,1,1209,988,1611,74,1413,164,1909,809,1062,194,1830,528,1064,710,2015,1,1492,1,1641,1028,1165,489,1959,1,1070,745,1713,1,1565,1,2078,872,1111,114,1791,308,1334,957,1884,1,1437,432,1706,720,1163,128,2091,1,1129,825,1624,434,1464,198,1898,965,1334,168,1811,54,1088,900,2160,312,1585,1,1745,728,1092,60,2016,461,1094,1093,1642,200,1534,314,2056,775,1098,440,1892,183,1257,734,1992,72,1469,1,1683,1037,1104,1,2163,48,1344,805,1739,1,1641,444,1940,740,1110,318,1888,1,1213,1008,2086,535,1538,132,1672,744,1339,98,2078,349,1118,895,1721,1,1493,1,2213,1080,1181,1,1888,450,1124,857,1968,174,1656,1,1690,752,1312,493,2163,62,1130,1005,1809,343,1538,74,1982,907,1237,1,1982,1,1363,758,2202,1,1517,560,1708,1036,1207,54,2110,1,1305,762,1714,458,1652,1,2159,873,1375,80,1911,1,1185,1123,2051,1,1533,229,1864,827,1152,377,2299,462,1154,770,1732,1,1629,1,2041,1029,1247,464,1931,332,1221,774,2205,212,1721,102,1827,962,1164,180,2135,138,1399,1074,1803,1,1557,468,2264,821,1337,1,2029,1,1172,853,2052,537,1588,1,1762,1161,1458,1,2262,182,1285,943,1799,1,1704,338,2125,788,1182,140,1971,517,1366,1053,2332,104,1660,1,1780,905,1188,590,2223,1,1231,855,1922,1,1589,1,2236,1114,1194,373,1991,1,1435,798,2117,1,1749,480,1798,847,1309,1,2356,400,1202,1158,1804,519,1605,84,2151,877,1447,1,2078,128,1279,990,2266,1,1644,60,1948,1077,1385,1,2223,583,1214,810,1822,348,1821,239,2414,812,1218,488,2060,1,1273,1085,2197,1,1666,350,1881,979,1224,1,2364,80,1527,861,1840,224,1637,492,2150,1197,1230,1,2092,108,1232,822,2399,523,1782,1,1852,824,1502,354,2267,1,1238,1167,1858,1,1712,68,2357,828,1315,192,2163,569,1357,830,2178,132,1744,54,1959,1109,1291,500,2471,228,1250,970,2031,62,1808,1,2192,1003,1433,110,2110,194,1507,1241,2356,360,1677,504,1925,840,1260,230,2353,1,1359,871,1894,607,1685,381,2450,1125,1542,1,2111,150,1449,1028,2220,60,1881,1,2033,980,1313,1,2439,510,1341,1133,2016,1,1803,1,2263,889,1278,585,2202,1,1280,854,2556,198,1770,234,1924,1255,1284,152,2355,368,1543,858,1930,84,1873,619,2439,860,1290,1,2194,90,1292,1190,2281,565,1725,200,1942,864,1592,1,2551,1,1298,1039,2007,425,1733,114,2354,1174,1302,138,2202,522,1304,949,2446,1,1915,374,1960,939,1308,524,2399,1,1514,1262,2097,1,1772,62,2584,1093,1415,72,2264,240,1579,878,2351,1,1757,559,1978,1173,1320,407,2542,140,1322,882,1984,553,1968,1,2318,884,1644,242,2228,380,1328,1240,2574,1,1773,1,2148,888,1464,1,2480,575,1377,1017,2031,158,1870,1,2506,1332,1529,643,2231,1,1443,941,2413,384,1938,1,2075,1075,1423,1,2675,1,1615,1220,2020,1,1797,628,2360,931,1421,1,2356,74,1545,955,2549,542,1846,1,2032,1248,1627,1,2487,1,1417,1087,2135,267,1964,1,2653,908,1362,390,2271,655,1411,1314,2419,1,1925,1,2050,912,1368,548,2642,415,1407,997,2193,1,1829,212,2458,1282,1374,68,2291,1,1717,1049,2710,1,2058,581,2121,920,1577,90,2554,252,1382,1229,2074,633,1845,1,2596,995,1663,164,2399,60,1461,1148,2430,1,1853,398,2225,1340,1499,277,2727,558,1593,930,2133,1,2047,1,2444,1084,1525,603,2331,1,1400,1245,2668,1,1869,1,2104,1140,1465,402,2627,54,1687,938,2147,98,1944,564,2806,1253,1410,1,2398,435,1495,942,2472,679,2042,258,2223,985,1699,150,2715,1,1527,1408,2128,1,1936,168,2557,948,1654,1,2450,570,1424,1023,2760,445,2015,1,2171,1269,1428,572,2636,1,1430,954,2302,1,2121,410,2686,1147,1434,62,2391,152,1764,1306,2514,239,1917,714,2158,1097,1440,1,2856,68,1573,993,2267,578,1962,1,2547,1392,1752,473,2411,264,1448,1159,2716,1,2117,224,2350,968,1452,1,2674,665,1454,1312,2182,1,2038,72,2835,972,1505,637,2551,1,1460,1113,2629,128,1949,80,2237,1379,1692,1,2807,102,1759,978,2200,420,2120,588,2570,1069,1583,1,2507,174,1472,1418,2922,621,1965,422,2279,984,1830,228,2748,1,1689,1183,2218,1,2002,270,2813,1364,1482,1,2490,594,1484,1033,2651,1,2212,1,2230,992,1488,732,2915,230,1490,1325,2385,272,2060,158,2612,1195,1494,104,2574,489,1818,998,2823,74,1997,600,2355,1481,1500,1,2781,1,1581,1158,2254,602,2172,98,2962,1063,1850,1,2511,132,1645,1408,2669,432,2013,1,2417,1061,1512,1,2927,738,1603,1010,2272,234,2122,434,2654,1349,1559,608,2554,1,1768,1014,2965,1,2211,180,2284,1248,1524,278,2795,1,1892,1470,2399,72,2037,659,2866,1020,1669,461,2653,1,1532,1022,2682,614,2118,1,2361,1396,1843,84,3070,440,1591,1272,2308,182,2300,1,2784,1107,1609,1,2571,618,1544,1429,2896,1,2164,282,2320,1032,1786,620,2882,164,1550,1034,2512,444,2116,108,3008,1519,1554,240,2628,1,1867,1099,2724,284,2250,713,2379,1040,1560,1,3004,1,1785,1389,2415,781,2085,60,2761,1193,1879,102,2727,242,1568,1274,3095,1,2093,74,2513,1397,1572,450,2883,667,1730,1050,2362,68,2318,138,2956,1052,1661,632,2631,493,1580,1574,2845,110,2140,1,2487,1267,1584,1,3114,1,1903,1209,2441,168,2140,763,2780,1413,1817,307,2704,1,1635,1062,2986,742,2361,1,2392,1064,1944,1,2946,104,1598,1492,2445,140,2174,458,3181,1165,1602,1,2760,642,1833,1070,2808,1,2248,267,2483,1565,1608,644,3083,1,1610,1111,2600,1,2328,294,2853,1334,1614,462,2691,1,1958,1437,3132,62,2245,648,2428,1163,1620,80,3036,464,1622,1129,2434,709,2165,192,3075,1464,2029,1,2711,1,1628,1334,2887,1,2354,1,2609,1088,1865,252,3231,654,1705,1585,2495,468,2290,1,2864,1092,1638,787,2835,114,1789,1094,3117,194,2189,537,2464,1534,1697,174,3015,323,2022,1098,2470,90,2441,660,3194,1257,1747,1,2817,1,1779,1469,2951,662,2234,1,2482,1104,1987,517,3198,1,1658,1344,2488,108,2292,1,2989,1641,1813,1,2771,818,1664,1110,3316,1,2443,1,2636,1213,1668,697,3059,72,1670,1538,2673,258,2229,1,3155,1339,1913,1,2915,198,2078,1118,2934,480,2280,733,2518,1493,1753,1,3298,1,1723,1181,2553,674,2449,519,2948,1124,2023,1,2811,1,1929,1656,3166,308,2253,110,2718,1312,1781,200,3150,678,1694,1130,2674,1,2374,1,3340,1538,1698,777,2831,80,1700,1237,3078,180,2549,84,2591,1363,1835,1,3267,488,2078,1517,2560,1,2277,684,3051,1207,1710,264,2965,312,1771,1305,3318,823,2285,150,2572,1652,2115,74,3160,1,1819,1375,2578,492,2484,182,3269,1185,1722,314,2912,743,1724,1533,3018,1,2439,523,2590,1152,1885,692,3442,1,1996,1154,2769,1,2309,1,3032,1629,1734,1,2908,1,2083,1247,3287,152,2510,835,2687,1221,1787,569,3220,60,1742,1721,2681,739,2408,318,3380,1164,2095,1,3008,500,1748,1399,3083,270,2386,1,2843,1557,1855,114,3359,702,1754,1337,2632,349,2614,1,3074,1172,2009,741,2931,1,1760,1588,3477,504,2349,272,2644,1458,1807,1,3291,1,2119,1285,2650,1,2388,809,3333,1704,1831,1,3010,1,2048,1182,3102,710,2562,1,2662,1366,2202,68,3479,343,1778,1660,2795,1,2373,1,3205,1188,1919,510,3114,745,1784,1231,3346,84,2517,1,2727,1589,1788,872,3279,585,1790,1194,2865,1,2588,1,3578,1435,1957,212,3014,98,2155,1749,3144,1,2397,720,2729,1309,2057,62,3481,278,1802,1202,2757,825,2405,1,3199,1605,2186,158,3054,1,1947,1447,3504,1,2681,565,2897,1279,1812,1,3323,900,2110,1644,2722,192,2553,1,3406,1385,1897,728,3132,1,1927,1214,3290,332,2429,1,2734,1821,1824,522,3611,90,2264,1218,2823,282,2669,775,3200,1273,1889,1,3112,524,1832,1666,3436,734,2492,194,2883,1224,2203,1,3435,1,2005,1527,2758,1,2453,284,3589,1637,2105,128,3071,805,1941,1230,3228,559,2707,1,2841,1232,1848,740,3554,1,1893,1782,2998,1,2469,553,3242,1502,1963,338,3194,1,2280,1238,3684,80,2477,744,2788,1712,2042,1,3442,62,1862,1315,2946,895,2784,1,3496,1357,2239,575,3111,1,1868,1744,3270,102,2582,1,3010,1291,1872,198,3680,857,1874,1250,2812,164,2656,373,3351,1808,1878,752,3131,307,1880,1433,3573,1,2737,72,2824,1507,2153,1,3455,1,2292,1677,2871,628,2554,907,3718,1260,1890,1,3298,200,1953,1359,3355,758,2525,542,2842,1685,2275,224,3635,1,2169,1542,2921,1,2744,132,3440,1449,1902,1,3171,762,2077,1881,3707,294,2668,104,2860,1313,1908,873,3552,348,1993,1341,3057,1,2653,1,3586,1803,1914,90,3220,548,2299,1278,3354,1,2841,827,3015,1280,2021,350,3831,168,2035,1770,2915,770,2565,1,3405,1284,2399,1,3318,1,1975,1543,3616,581,2573,228,3089,1873,1932,1,3566,774,1934,1290,2902,74,2839,633,3763,1292,2087,962,3250,1,2217,1725,3493,1,2589,354,2914,1592,2011,323,3766,1,2335,1298,3059,230,2656,821,3410,1733,1950,558,3329,84,1952,1302,3844,853,2853,1,2932,1304,2370,1,3587,603,2061,1915,3027,1,2613,1,3732,1308,2015,1,3380,943,2115,1514,3438,1,2752,1,2950,1772,2249,788,3855,128,2149,1415,3153,564,2921,1,3481,1579,1974,1,3338,360,2450,1757,3725,68,2637,905,3011,1320,1980,108,3697,234,2265,1322,2974,855,2645,1,3938,1968,2383,381,3311,138,1988,1644,3551,98,2891,174,3185,1328,2173,570,3819,798,1994,1773,2992,1,2813,308,3494,1464,1998,847,3479,572,2000,1377,3906,1,2698,1,3160,1870,2004,1,3675,212,2407,1529,3069,1,2900,877,3766,1443,2338,1,3418,1,2012,1938,3522,990,2746,1,3075,1423,2450,140,3998,110,2018,1615,3028,368,2693,578,3637,1797,2069,312,3371,810,2330,1421,3819,1,3031,1,3040,1545,2028,812,3732,1,2030,1846,3278,132,2709,240,3938,1627,2141,665,3504,314,2480,1417,3564,1,2814,979,3058,1964,2040,1,3928,637,2199,1362,3064,861,2952,68,3651,1411,2455,1,3442,1,2137,1925,4095,242,2733,1,3322,1368,2345,374,3839,822,2054,1407,3161,588,2878,1,3856,1829,2262,824,3487,180,2131,1374,3709,318,2978,621,3094,1717,2064,1,4043,1,2538,2058,3100,1,2810,828,3667,1577,2070,1,3589,102,2181,1382,3923,830,2765,407,3173,1845,2574,594,3807,1,2145,1663,3118,1,3092,1,4109,1461,2082,182,3471,970,2084,1853,3648,380,2920,98,3279,1499,2088,1003,4032,1,2090,1593,3364,114,2830,90,3662,2047,2416,80,3491,72,2515,1525,4062,600,3030,840,3148,1400,2100,343,3893,1,2293,1869,3154,871,2805,602,3946,1465,2527,1,3680,384,2452,1687,3721,1,2850,1,3377,1944,2112,104,4203,1028,2114,1410,3323,1,3103,1,3727,1495,2191,980,3531,224,2283,2042,4029,1,2930,1,3184,1699,2317,138,3954,608,2653,1527,3190,1,2837,889,4143,1936,2130,1,3622,1,2132,1654,3773,854,3161,252,3299,1424,2624,1,4095,1,2138,2015,3208,659,2884,390,3853,1428,2142,1,3707,858,2144,1430,4222,1,3017,614,3257,2121,2261,860,3939,1,2457,1434,3484,415,3108,332,4036,1764,2154,74,3591,140,2587,1917,3862,228,2877,864,3321,1440,2287,618,4251,150,2162,1573,3291,1039,2988,1,3788,1962,2599,72,3630,620,2365,1752,4066,1,3134,1,3504,1448,2339,102,3983,949,2227,2117,3262,1,3075,230,4336,1452,2489,939,3763,1,2180,1454,3925,713,2909,1,3274,2038,2243,398,4200,258,2646,1505,3280,1,3280,1093,3830,1460,2389,152,3724,338,2505,1949,4248,878,2968,108,3292,1692,2635,1,4088,192,2380,1759,3455,1,2933,84,4192,2120,2273,667,3671,882,2204,1583,3887,1,3242,402,3310,1472,2208,884,4371,632,2257,1965,3554,1,3016,1,3951,1830,2214,234,3855,104,2659,1689,4156,435,2957,888,3328,2002,2537,194,4108,1,2222,1482,3435,1017,3231,1,4310,1484,2760,1,3764,74,2359,2212,3900,1,2973,742,3569,1488,2329,1,4310,941,2582,1490,3352,110,3130,264,3957,2060,2238,1075,3731,445,2240,1494,4453,1,3321,1,3423,1818,2244,642,4132,68,2695,1997,3370,1,3104,931,4216,1500,2423,410,3906,644,2252,1581,3942,955,3005,1,3566,2172,2748,348,4419,1,2319,1850,3388,1,3264,1,4069,1645,2604,1,3800,1087,2337,2013,4246,648,3172,198,3503,1512,2268,908,4250,350,2270,1603,3633,240,3029,709,4474,2122,2274,1,3791,1,2835,1559,3984,158,3313,912,3485,1768,2333,98,4390,1,2282,2211,3587,997,3045,1,3998,1524,2743,654,3938,270,2288,1892,4447,200,3162,242,3665,2037,2371,1,4203,1049,2294,1669,3479,354,3418,1,4347,1532,2298,920,3831,1,2528,2118,4164,108,3128,1,3454,1843,2680,272,4603,420,2767,1591,3460,660,3077,995,4040,2300,2310,150,3939,1,2312,1609,4353,1148,3342,662,3561,1544,2779,422,4247,114,2649,2164,3539,1,3093,1,4525,1786,2533,1,4043,930,2425,1550,4151,1,3287,1,3490,2116,2507,1084,4463,1,2467,1554,3729,80,3405,1,4135,1867,2334,360,3891,697,2803,2250,4600,1,3158,1140,3675,1560,2340,1,4369,152,2342,1785,3514,938,3196,110,4396,2085,2882,1,3934,381,2348,1879,4110,733,3510,128,3808,1568,2352,1,4614,942,2535,2093,3639,278,3298,674,4155,1572,2358,985,4062,90,2697,1730,4485,1,3149,1,3544,2318,2503,164,4335,1,2882,1661,3732,1,3420,948,4700,1580,2473,678,4030,432,2372,2140,4152,1023,3278,102,3562,1584,2965,1,4599,777,2378,1903,3609,72,3234,1,4302,2140,2382,434,3971,954,2384,1817,4620,252,3499,368,3580,1635,2760,1147,4379,282,2390,2361,3825,684,3189,1,4509,1944,2394,1,4143,1,2875,1598,4194,1,3244,1097,3707,2174,2400,1,4756,1,2801,1602,3604,993,3561,461,4208,1833,2924,284,4011,1,2491,2248,4559,1,3286,80,3857,1608,2412,743,4490,1159,2541,1610,3693,440,3405,1,4682,2328,2418,968,4062,692,2479,1614,4368,104,3498,168,3807,1958,2424,132,4647,374,3008,2245,3640,212,3237,972,4250,1620,2777,114,4251,1,2670,1622,4846,1113,3245,158,3652,2165,2923,1,4496,444,2438,2029,3711,1,3524,739,4637,1628,2442,258,4108,978,2793,2354,4325,1,3424,74,3670,1865,2448,1069,4812,84,2529,1705,3977,407,3312,1,4292,2290,2677,702,4091,1,2947,1638,4606,307,3654,984,3688,1789,2460,1,4552,741,2569,2189,3694,1183,3285,380,4863,1697,2988,1,4248,1,2468,2022,4320,1,3293,450,3972,2441,2825,1,4739,1033,2474,1747,3712,809,3642,1,4334,1779,2478,992,4190,1,2547,2234,4837,493,3309,710,3797,1987,2675,1,4647,1,3054,1658,3843,1,3317,1195,4666,2292,2621,384,4234,294,2545,1813,4451,998,3602,1,3785,1664,2995,745,4967,1,2725,2443,3748,264,3469,1,4531,1668,2563,1,4310,1158,2504,1670,4696,1,3508,1,3939,2229,2617,1063,4618,174,2703,1913,4017,1,3752,1,4868,2078,2873,458,4191,108,3019,2280,4441,720,3357,1061,3778,1753,2749,1,4873,72,2522,1723,3881,1010,3394,825,4418,2449,3132,1,4211,164,2908,2023,4978,390,3654,1,4072,1929,2532,84,4643,1014,2683,2253,3983,138,3563,462,4756,1781,2597,1248,4419,1,2540,1694,4573,1,3521,415,3855,2374,2544,1,4983,728,3055,1698,3887,464,3680,1020,4564,1700,2550,1,4353,1,2552,2549,4815,1022,3442,1,3832,1835,3140,270,4758,1,2558,2078,3838,775,3413,1,5116,2277,2759,110,4332,1272,2797,1710,4488,224,3820,734,3850,1771,2719,1107,4923,468,2937,2285,4113,98,3429,140,4502,2115,2657,1,4447,272,3194,1819,5015,1,3437,1032,3868,2484,2580,805,4774,398,2671,1722,3874,1034,3773,1,4865,1724,3150,1,4311,740,2787,2439,4530,168,3453,1,4182,1885,2592,74,5143,1099,2594,1996,3892,1,3634,180,4603,2309,3022,1040,4331,1,2713,1734,4954,744,3775,517,3904,2083,2741,128,4806,1,3127,2510,3910,402,3556,1193,5054,1787,2610,308,4525,228,2985,1742,4572,1274,3552,1,3922,2408,3139,1,5015,1,2618,2095,4132,1,3881,435,4717,1748,2622,857,4394,1050,2685,2386,5208,182,3718,90,4041,1855,2699,1052,4892,752,2869,1754,4209,1,3509,278,4983,2614,2634,230,4391,480,3194,2009,4614,1,3810,1267,3958,1760,3046,1,5182,1,2781,2349,3964,1209,3525,312,4628,1807,3198,519,4614,80,2648,2119,4966,1,3533,758,4294,2388,2893,1,4880,1062,3033,1831,3982,1,3895,114,5230,2048,2658,1064,4431,410,2660,2562,4808,314,3549,1,4126,2202,2664,762,5144,74,3240,1778,4043,1,3684,1165,4699,2373,2827,282,4540,873,2672,1919,5178,1070,4005,1,4203,1784,3318,1,4907,102,2678,2517,4121,488,3620,234,5093,1788,3065,174,4620,1111,2684,1790,4759,827,3760,132,4109,2588,2688,1334,5363,284,2690,1957,4305,1,3911,770,4712,2155,2694,1,4491,318,3323,2397,5056,1,3628,1163,4119,2057,2700,1,5056,492,2775,1802,4247,1129,3658,1,5253,2405,3247,774,4552,1,2708,2186,4740,1,3957,1,4337,1947,2712,523,5199,1334,2714,2681,4131,90,3802,1,4851,1812,2984,1088,4682,1,2720,2110,5373,1,3629,1,4084,2553,3113,420,4995,1,3380,1897,4137,821,4041,1092,5147,1927,2730,104,4655,128,2732,2429,4782,1094,3645,853,4102,1824,3283,1,5378,422,3152,2264,4145,1,3736,1,4933,2669,2742,1,4571,1098,2955,1889,5202,500,4027,343,4120,1832,2815,1257,5039,240,2750,2492,4467,1,3800,1,5462,2203,2754,1,4812,788,3336,2005,4877,150,3677,1104,4335,2453,2849,1,5314,1,3013,2105,4144,1344,3992,1,4838,1941,3398,1,4611,504,2768,2707,5364,905,3764,192,4433,1848,2935,242,5171,1110,2833,1893,4235,180,3923,855,5206,2469,2778,1213,4631,1,3177,1963,5005,84,4121,1,4281,2280,3060,294,5511,1,3343,2477,4379,1,3717,1339,4921,2042,2790,798,4837,1,2792,1862,5236,1118,3877,152,4319,2784,3398,1,5127,847,2798,2239,4198,194,4044,510,5468,1868,2802,432,4671,1181,2804,2582,4908,80,3945,182,4271,1872,3209,1124,5435,138,2863,1874,4497,877,3749,1,4959,2656,2911,332,4758,434,3379,1878,5622,132,4070,1312,4228,1880,2820,1,5218,1,3256,2737,4317,1130,3765,1,5296,2153,3504,1,4868,1,3085,2292,5051,1,3814,1,4529,2554,2981,810,5547,1237,2834,1890,4361,1,4243,108,4964,1953,2838,1363,4774,812,3007,2525,5397,461,3789,1,4496,2275,2844,565,5294,1,3415,2169,4270,1,3870,1207,5608,2744,3294,140,4865,1,2852,1902,5023,1305,4122,440,4282,2077,3427,1,5492,198,2858,2668,4288,1,3813,861,5162,1908,2862,98,4983,1375,3273,1993,5550,338,4012,522,4300,2653,2929,1185,5259,1,3021,1914,4634,1,4177,1,5386,2299,3112,822,4791,1,3589,2841,5034,524,3974,1152,4318,2021,2880,444,5736,824,2949,2035,4455,1154,3876,80,5151,2565,3463,200,4848,252,2888,2399,5435,110,4281,1,4642,1975,3364,1,5303,1247,3157,2573,4342,828,4054,1,5612,1932,2898,1221,5015,559,3123,1934,5250,1,3869,830,4354,2839,2904,1,5578,158,3570,2087,4360,1,4219,1164,5090,2217,2910,553,4948,1,2983,2589,5747,1399,3885,1,4419,2011,3552,970,5467,308,2918,2335,4378,450,4032,1,5549,2656,3049,1,4871,1337,3003,1950,5161,1,4304,1,4618,1952,2928,1172,5735,1,3031,2853,4689,1,3909,575,5132,2370,3353,1,5054,1,3523,2061,5506,840,4006,1458,4521,2613,2940,1,5447,1,3115,2015,4414,1285,4361,871,5866,2115,3566,138,4911,84,3369,2752,5227,1,3933,348,4780,2249,3179,1,5700,1182,2954,2149,4643,312,4138,258,5174,2921,2958,1366,4960,98,3229,1974,5773,192,4325,1,4444,2450,2964,1,5454,980,3559,2637,4450,350,4000,1188,5619,1980,2970,1,5182,458,2972,2265,5202,1231,3965,314,4462,2645,3707,542,5891,1,3207,2383,4468,889,4304,102,5365,1988,3253,90,5042,1194,3141,2891,5596,128,4180,854,4480,2173,3091,1435,5562,140,3478,1994,4808,1,3989,194,5815,2813,3067,1,4991,114,3595,1998,5351,462,4478,1309,4498,2000,3000,858,5781,354,3002,2698,4583,1202,4161,1,5258,2004,3607,1,5178,860,3105,2407,5970,548,4072,464,4860,2900,3012,318,5523,1447,3145,2338,4659,1,4423,164,5685,2012,3449,1279,5031,1,3020,2746,5437,864,4082,1,4534,2450,3024,1,5951,264,3763,2018,4629,1,4037,1385,5300,2693,3263,84,5152,581,3465,2069,5686,1214,4382,1,4593,2330,3643,468,5590,1,3038,3031,4806,104,4053,1,6005,2028,3042,949,5253,1218,3223,2030,5328,1,4293,1,4570,2709,3325,1273,5843,939,3050,2141,4942,1,4521,360,5451,2480,3125,198,5091,150,3714,2814,5922,1,4077,1224,4727,2040,3520,212,5713,1,3062,2199,4594,1527,4085,558,5746,2952,3679,1,5184,1,3068,2455,5429,381,4465,878,4913,2137,3155,1,6142,1230,3513,2733,4665,603,4347,1,5384,2345,3259,1232,5378,132,3080,2054,5864,102,4188,1,4691,2878,3084,882,5655,200,3703,2262,4630,1,4516,1502,5984,2131,3090,168,5254,884,3373,2978,5412,1238,4125,270,4880,2064,3715,152,5978,564,3261,2538,4648,1,4133,1,5612,2810,3545,1,5218,1315,3211,2070,6112,888,4624,1,4660,2181,3347,1357,5736,1,3110,2765,4977,1,4210,1017,5836,2574,3397,480,5364,1,3828,2145,5495,272,4157,1291,4678,3092,3120,368,6124,80,3122,2082,4907,1250,4512,1,5539,2084,3906,941,5211,519,3187,2920,5889,1,4322,570,5009,2088,3233,1,5859,1433,3375,2090,4702,1,4409,1,6231,2830,3138,1507,5231,1,3213,2416,5653,572,4538,104,4714,2515,3593,1,6027,332,3812,3030,4876,931,4197,1260,5510,2100,3217,1,5468,1,3289,2293,6108,1359,4205,955,4815,2805,3787,1,5787,108,3650,2527,4738,1,4733,90,6005,2452,3271,1,5302,1542,3164,2850,5651,1,4432,488,4750,2112,3168,1449,6282,1,3170,2114,5073,374,4380,1,5613,3103,3341,578,5314,908,3938,2191,5956,1,4590,1313,4995,2283,3486,1,5884,1,3182,2930,4817,1341,4245,1,6170,2317,3927,278,5547,1,3188,2653,5580,912,4253,1,5134,2837,3192,492,6138,1278,3297,2130,4792,1,4687,997,5641,2132,3337,1280,5372,1,3657,3161,6381,174,4366,338,4804,2624,3204,150,5964,523,3847,2138,5039,637,4277,1284,6016,2884,3210,1049,5458,1,3478,2142,5695,1543,4778,1,4822,2144,3859,110,6299,920,3218,3017,4828,158,4330,138,5820,2261,3222,380,5550,1290,3517,2457,6077,1,4559,1,4840,3108,3689,1292,5919,588,3230,2154,5188,995,4668,282,6364,2587,3295,224,5479,1,3883,2877,5664,1,4400,1592,4858,2287,3319,621,6276,1,3705,2162,4864,1298,4372,500,5678,2988,3954,1,5411,152,3439,2599,6323,90,4713,98,5279,2365,3252,930,5963,1302,3254,3134,4882,284,4589,384,6143,2339,3258,1304,5612,1084,3260,2227,5869,1,4349,594,5127,3075,3515,108,6495,1,3919,2489,4971,140,4852,1308,5763,2180,3737,504,5560,212,3272,2909,6136,1514,4365,1,4912,2243,4062,1,6111,1,3391,2646,5067,84,4373,938,6397,3280,3475,1,5471,1415,3820,2389,5748,1,4819,1,4983,2505,3461,1579,6303,1,3612,2968,5312,1,4389,228,5762,2635,3383,942,5735,600,3955,2380,6490,348,4554,1320,5045,2933,3300,1,6117,985,3302,2273,5081,1322,4772,1,6255,2204,3967,602,5540,390,3308,3242,5790,510,4413,1,5297,2208,3828,180,6510,1644,3314,2257,4972,948,4659,350,5804,3016,3425,1328,5610,1,3320,2214,6309,230,4962,1023,5135,2659,3324,415,6095,110,4143,2957,4990,1,4437,1464,6644,2537,3330,1,5773,1,3332,2222,5968,1377,4546,114,5002,3231,4032,954,6395,1,3409,2760,5008,608,4877,1,6013,2359,3599,164,5571,1529,3344,2973,6499,1,4684,1,5259,2329,3348,1443,6263,182,3547,2582,5428,1,4469,1,6286,3130,3833,354,5634,1,4088,2238,5874,1097,4850,1423,5111,2240,3360,1,6658,659,3362,3321,5085,1615,4544,993,5917,2244,4039,128,5815,1,3886,2695,6316,1,4493,294,5393,3104,3372,614,6183,1421,3374,2423,5303,398,5031,158,6542,2252,3685,1545,5631,234,3489,3005,6098,1,4693,1,5163,2748,3583,102,6534,968,4063,2319,5080,522,4517,1627,6062,3264,3390,1,5764,1,3392,2604,6732,1417,4931,618,5092,2337,4172,1,6227,1,3477,3172,5098,972,4636,524,6478,2268,3581,1,5951,1362,3487,2270,5995,620,4768,1113,5241,3029,3408,1411,6675,402,3897,2274,5488,360,4928,1,5972,2835,3414,1,5691,1,4099,3313,6467,1,4624,1368,5128,2333,3683,978,6385,1,3733,2282,5193,1407,4728,168,6742,3045,4248,559,5711,1069,3577,2743,6000,1,5081,381,5545,2288,3505,1,6592,1374,3434,3162,5253,1,4810,1,6014,2371,3929,1717,5922,553,3621,2294,6709,984,4626,1,5164,3418,3757,98,6356,84,4188,2298,5170,114,4980,1577,6466,2528,3450,1,5889,104,3974,3128,6042,1382,4605,1,5339,2680,4147,1,6898,224,3458,2767,5454,1,4613,667,6229,3077,3462,1033,5771,1663,3464,2310,6496,575,5094,240,5200,2312,3468,1461,6376,992,3470,3342,5553,632,4718,132,6759,2779,3625,1,5984,1,4310,2649,6163,410,4698,1499,5265,3093,4048,1,6700,1,3541,2533,5224,1593,5204,1,6165,2425,4224,1,5894,368,3805,3287,6868,1,4653,998,5585,2507,3492,1,6500,1525,3993,2467,5242,242,4894,1,6579,3405,3767,1400,5884,1,3500,2334,6343,1,5058,150,5357,2803,3617,1158,6863,164,4207,3158,5260,1,4844,1465,6140,2340,3858,1,6124,1063,3512,2342,6586,1687,4685,1,5523,3196,4256,90,6447,542,3518,2882,5278,228,5107,1,6997,2348,4025,1,5871,1410,3795,3510,6168,1061,4983,642,5333,2352,3528,1495,6819,1,3530,2535,5649,308,4816,1010,6182,3298,3534,192,5922,1,4344,2358,6869,644,5241,1699,5369,2697,3540,1,6550,98,3542,3149,5590,1527,4725,374,6646,2503,4255,1014,6108,174,3548,2882,6210,152,4915,230,5752,3420,3619,1,7031,1654,3896,2473,5332,1,5215,548,6351,2372,3558,1424,5931,648,3560,3278,6765,1,4749,420,5481,2965,4073,1,6678,1,4310,2378,5350,1020,4798,1428,6914,3234,3653,709,6087,194,3572,2382,6299,1430,5162,1022,5362,2384,4447,1,6855,312,4162,3499,5368,422,4773,1,6445,2760,3582,581,6170,1434,3584,2390,7162,108,5020,102,5543,3189,3799,1764,6602,1,3687,2394,5745,168,5340,654,6736,2875,3594,1,5991,1107,4315,3244,6325,1,4906,1440,5655,2400,3661,314,7081,380,3879,2801,5404,1573,4805,1,6361,3561,4430,1,6011,1,3608,2924,6807,1032,5214,1,5796,2491,3769,234,6666,1752,3614,3286,5561,1,5062,1034,7120,2412,3618,1448,6299,1,4184,2541,6517,558,4900,1,5434,3405,3624,1,6947,660,4525,2418,5736,1,5271,1452,6350,2479,3821,1099,6183,138,3632,3498,7038,1454,5018,603,5531,2424,4363,662,6768,1040,3638,3008,5565,384,4853,252,6930,3237,3973,1,6071,1505,3644,2777,6378,198,5466,318,5470,2670,4169,1460,7259,1,3739,3245,5914,1193,4869,110,6475,2923,3935,1,6323,1,4430,2438,6856,104,4930,1692,5547,3524,3660,564,6772,1,4185,2442,5494,1759,5329,432,7100,2793,4399,1,6158,1,3861,3424,6551,697,4893,180,5873,2448,3672,1050,7107,1583,3674,2529,5679,1,5202,1,6434,3312,3678,1472,6131,1052,3963,2677,7269,434,5318,200,5787,2947,3811,140,6755,1,4490,3654,5627,102,4917,1830,6916,2460,4248,158,6397,733,3692,2569,6533,1689,4925,90,5542,3285,4435,390,7250,1,3698,2988,5591,570,5481,1209,6698,2468,3702,674,6171,1482,4256,3293,6946,240,5207,1,5669,2825,4045,1484,6902,1,3710,2474,5990,182,4949,572,7396,3642,3793,1062,6191,461,4459,2478,6504,1,5429,1488,5760,2547,3720,174,7162,1064,3783,3309,5584,1490,5038,678,6670,2675,4620,1,6510,258,3728,3054,7224,1,5086,1,5969,3317,4306,440,6843,1494,3734,2621,5602,1165,5479,242,7006,2545,3839,1818,6320,1,3740,3602,6750,1,5032,1070,5614,2995,3941,1,7424,1,4602,2725,5620,128,4997,1500,6560,3469,3913,1,6406,578,4124,2563,7103,1581,5561,1,5632,2504,4507,1111,6887,684,4064,3508,5638,1,5192,104,7333,2617,3762,1,6499,1850,3835,2703,6588,1,5272,444,5919,3752,3768,1645,7223,1,3770,2873,6062,1,5448,398,6643,3019,4401,1,6328,1,4682,3357,7494,1163,5037,1512,5668,2749,3780,1,7078,1,3981,2522,5735,1603,5142,1129,7139,3394,4543,114,6311,1,4329,3132,6630,1,5474,743,6065,2908,4015,1,7427,1559,3794,3654,5963,1,5337,1,6717,2532,3798,1768,6542,108,3931,2683,7240,692,5250,1,5704,3563,3804,1,6975,1088,4567,2597,5883,332,5688,1524,7515,2540,4103,402,6478,1,3915,3521,6672,1892,5126,264,5722,2544,4688,588,7368,450,4165,3055,5811,1092,5160,1,6877,3680,3822,1,6475,1669,3824,2550,7410,1,5628,1094,5740,2552,3917,1532,7048,621,4377,3442,6129,164,5109,98,7186,3140,3834,739,6675,1,4662,2558,6851,1,5117,1843,5859,3413,4189,1098,7671,1,4009,2759,5877,1591,5613,1,6759,2797,4615,1,6411,1257,3848,3820,7253,180,5133,1,6249,2719,3852,1,7170,1609,3854,2937,5829,594,5398,702,7472,3429,4438,1544,6431,1,4087,2657,6949,1104,5734,1,5794,3194,3864,1,7430,132,4639,3437,5800,741,5157,1786,6770,2580,3943,110,6709,1,4504,2671,7635,1550,5165,128,5961,3773,4837,338,7126,1,3878,3150,6095,1,5604,1,7373,2787,3882,1110,6471,1554,4237,3453,6798,458,5477,410,5897,2592,4210,1867,7654,1213,3890,2594,6225,252,5189,182,6951,3634,4123,600,6550,1,4716,3022,7306,1,5630,1560,5848,2713,4457,710,7229,270,3985,3775,5854,1785,5205,212,7748,2741,4758,108,6759,602,3908,3127,6840,1,5213,1118,6280,3556,3912,1,7499,1879,4516,2610,5975,1,5830,192,6943,2985,3918,1568,6531,462,3920,3552,7652,1,5229,745,5937,3139,3924,1181,7304,168,4868,2618,6041,1,5441,1572,7366,3881,3930,272,6682,1124,3932,2622,6882,1730,5705,1,6183,2685,4723,464,7791,1,4065,3718,6087,1,5354,1,7093,2699,4505,1,6863,1661,3944,2869,7425,1312,5524,608,5920,3509,3948,1580,7286,150,4309,2634,6400,1,5708,1130,7677,3194,4021,1,6591,720,4860,3810,6967,194,5277,1584,5938,3046,4067,1,7657,90,4195,2781,6227,1903,5285,1,6938,3525,4820,1237,6611,1,3968,3198,7906,1,5937,468,6353,2648,4352,659,7283,1817,4111,3533,5962,1,5619,1,7527,2893,4075,1635,6869,110,4153,3033,7165,420,5309,1,6155,3895,4553,258,7803,614,4783,2658,5980,1207,5760,1944,6980,2660,3990,102,6803,348,4299,3549,7486,1598,5457,1305,5992,2664,4842,132,7475,1,4569,3240,5998,728,5376,422,7906,3684,4002,152,6700,1602,4004,2827,7164,1,5875,1,6010,2672,4008,1833,7683,1,4221,4005,6417,618,5540,114,7081,3318,4014,350,6914,1185,4892,2678,7782,278,5460,1608,6356,3620,4020,1,7438,775,4022,3065,6034,1610,5961,620,7546,2684,5015,98,6772,1,4028,3760,7103,1152,5452,1,6480,2688,4171,734,8030,1614,4143,2690,6052,1,5650,1154,7064,3911,4405,1958,6731,198,4617,2694,7677,1,5838,138,6111,3323,4355,1,7415,1,4855,3628,6376,1,5468,1620,7867,2700,4050,1247,7081,1,4052,2775,7092,1622,5598,805,6082,3658,4867,1,7788,1221,4058,3247,6088,1,5905,354,7338,2708,4193,1,6771,2029,4303,3957,8002,740,5692,174,6207,2712,4732,1628,7572,104,4383,2714,6550,1164,5488,480,7636,3802,4074,1,6888,282,5054,2984,7134,264,6041,1865,6118,2720,4080,200,8008,1,4718,3629,6281,1705,5445,1,7148,3113,4946,1,7038,744,4155,3380,7739,667,5500,1,6545,4041,4092,1337,7534,1638,4094,2730,6231,432,6020,1,8191,2732,4339,1789,6831,1172,4100,3645,7422,140,5469,632,6447,3283,4477,284,7943,1,4927,3152,6160,192,5514,1697,7269,3736,4697,1,6988,1,4112,2742,7968,2022,5942,434,6376,2955,4939,1,7603,1,4297,4027,6249,1,5493,1285,7829,2815,4439,1,7100,1747,4744,2750,7218,114,5842,224,6190,3800,4128,1779,8171,360,4130,2754,6668,752,6189,1,7232,3336,4134,1182,6944,1,4963,3677,7803,1,5714,1987,6208,2849,4140,488,7729,1366,4243,3013,6323,1658,5525,1,8067,3992,4975,1,6911,1,4554,3398,7321,1,5994,194,6724,2768,4745,461,7959,1813,4154,3764,6299,1188,5818,1,7274,2935,4158,1664,7250,1,4160,2833,8269,158,5622,1231,6244,3923,4345,758,7635,1,5135,2778,6250,642,6020,1668,7816,3177,4549,270,7090,440,4269,4121,7451,1670,5672,492,6262,3060,5178,1194,8208,1,4178,3343,6268,138,5772,644,7544,3717,4295,1,7012,1913,4273,2790,7846,1,6232,762,6602,2792,4267,2078,7679,1,4261,3877,6705,523,5716,102,8254,3398,4793,1,7224,1,5035,2798,7344,1309,5597,1753,6298,4044,4542,228,8093,272,4202,2802,6495,1723,6072,1202,7358,2804,5076,648,7011,180,4809,3945,8154,444,5674,1,6737,3209,4212,1,7892,2023,4597,2863,6666,1,5902,1,7937,3749,4218,1929,7068,827,4220,2911,7597,368,6165,1,6334,3379,4327,1,8427,1279,5253,4070,6340,108,5637,1781,7551,2820,4230,770,7333,1,4232,3256,7959,1694,5728,1,6425,3765,5215,198,7767,230,4461,3504,6521,1385,6281,140,8269,3085,4242,500,7172,1698,4244,3814,7428,654,5944,1214,6563,2981,4385,1700,8202,294,4857,2834,6903,1,5778,774,7442,4243,4254,182,7091,128,5144,2838,8399,1,6193,1835,6388,3007,4260,1218,7882,1,4262,3789,6394,2078,5917,1,8037,2844,5119,450,7427,1273,4519,3415,7567,1,5693,1,6894,3870,4272,1,8367,1710,4274,3294,6412,104,6290,504,7484,2852,4936,1771,7162,200,4669,4122,8133,1224,5709,1,6424,3427,4284,660,7991,821,5143,2858,6430,1,5717,2115,8510,3813,4290,374,7307,1,4905,2862,7549,1819,6414,278,6555,3273,5155,853,8235,662,4298,4012,6755,1,5733,1,7784,2929,4716,1230,7410,1722,4635,3021,8340,1,6069,110,6460,4177,4381,1724,7899,1232,4449,3112,6897,234,6228,1,8174,3589,4541,1,7191,1,5179,3974,7637,98,5757,1885,6605,2880,4937,164,8571,1,4471,2949,6484,1996,5896,1,7615,3876,5364,212,7314,510,4328,3463,8116,788,6291,1238,6929,2888,4403,1,7962,1734,4953,4281,6699,1,6087,697,8402,3364,4338,2083,7472,1,4340,3157,7844,1,5789,458,6681,4054,4445,1315,8327,1,5294,2898,6573,1,6464,1787,7610,3123,4350,1,7425,1357,4581,3869,8688,1742,5805,1,6843,2904,5294,282,8119,1,4358,3570,6538,380,5813,1,8285,4219,5074,855,7271,2095,4364,2910,7638,1291,6403,1,6609,2983,4765,1748,8568,1,4627,3885,7016,1,5876,1250,7652,3552,4374,1,7654,674,5468,2918,8206,1,5837,1855,6767,4032,4531,462,8104,1,4719,3049,6887,1754,6332,798,8632,3003,5263,1433,7354,284,4495,4304,7680,132,6081,1,7025,2928,4392,1,8480,2009,4585,3031,6774,847,6154,150,7851,3909,4398,1760,7331,464,4483,3353,8592,678,6521,1,6675,3523,5070,1,8075,384,5287,4006,6610,1260,5990,1807,8295,2940,4410,1,7652,1,4813,3115,7722,2119,5885,1359,6622,4361,5299,1,8787,877,5049,3566,6675,1,6384,1,7974,3369,4422,240,7438,1831,4424,3933,8375,1,6255,168,6640,3179,4661,2048,8283,522,4533,2954,7089,1,6120,1,8588,4138,4868,1,7391,1449,5323,2958,7764,468,6439,2202,6975,3229,4633,684,8548,108,4442,4325,6664,1778,5925,1,7879,2964,5462,524,7677,1,4448,3559,8758,1313,5933,810,7210,4000,4452,308,8216,1919,4527,2970,6813,152,6667,1341,8356,2972,4458,1784,7431,242,5201,3965,8029,812,5949,1,6791,3707,4464,114,8774,1,5406,3207,7048,1,5957,1788,7820,4304,4579,1278,7600,1,4735,3253,8429,1790,6533,390,6712,3141,5550,1,8207,1280,4922,4180,6718,743,5973,559,8933,3091,4482,1,7803,1957,4484,3478,7907,1,6303,1,6730,3989,5129,2155,8620,192,4557,3067,7185,1284,6488,692,7862,3595,4494,861,7598,102,5426,4478,8712,553,5997,2057,6921,3000,4909,1,8406,1,5145,3002,6754,1802,6084,1,8446,4161,5460,1,7511,1,4508,3607,8074,128,6681,312,7258,3105,4859,1290,8931,2186,4514,4072,6833,1,6365,822,7904,3012,4518,1947,7782,1292,4520,3145,8589,1,6166,1,7126,4423,4524,110,8324,1,5612,3449,6863,824,6540,1812,8774,3020,5177,1,7702,739,4729,4082,8035,2110,6045,1,6802,3024,5443,194,8786,212,4887,3763,6808,314,6142,1298,8173,4037,4781,294,7571,1897,5252,3263,9018,150,6667,1,6820,3465,4548,1927,8339,828,4550,4382,7385,480,6110,1,8536,3643,4711,1302,7867,1,5467,3038,8041,702,6325,1824,6891,4053,4657,830,8950,1304,4562,3042,6844,2264,6774,1,8151,3223,5562,398,7611,1,4568,4293,8566,1,6093,741,7313,3325,5225,224,8510,1889,4843,3050,6862,1308,6467,1,9023,4521,4777,1832,7740,1,4821,3125,8245,1,6618,1514,6953,3714,4584,104,8787,174,5634,4077,6880,1,6256,2203,8067,3520,4943,138,8008,1,4592,3062,8939,2005,6125,1,6892,4085,5515,1415,8427,318,4598,3679,7126,542,6717,1,8764,3068,4709,1,7730,2105,4604,4465,8058,1,6448,152,7286,3155,4879,1941,9211,710,5029,3513,7377,1,6202,402,8072,4347,5273,1,7691,840,5610,3259,8656,1320,6917,1848,6928,3080,4769,1,8559,1,4622,4188,6934,1893,6232,1322,8977,3084,5773,871,7968,488,5289,3703,8189,1,6173,198,7409,4516,5053,158,8879,1963,4747,3090,7283,745,6799,128,8175,3373,4638,2280,7731,1,4640,4125,9165,1,6427,1,7175,3715,4644,252,8687,1328,5575,3261,7071,1,6197,2042,8799,4133,4650,548,7937,132,4652,3545,8142,1862,6769,228,7161,3211,5739,1,9119,140,4658,4624,7125,1464,6213,1,8389,3347,4741,1,8067,2239,4664,3110,8799,492,6532,1377,7000,4210,5027,1868,8559,1,5366,3397,7473,1,6921,1,9272,3828,4674,720,7832,1,5815,4157,8351,200,6237,1872,7018,3120,4680,1529,9049,889,4833,3122,7024,1874,6468,581,8198,4512,5623,1,7882,1443,4797,3906,9084,1,6774,114,7572,3187,4692,854,8626,1878,5074,4322,7042,230,6574,1,8806,3233,5430,1880,8208,1,4827,3375,8508,1423,6269,1,7054,4409,4704,410,9318,98,5647,3138,7241,1,6800,2153,8347,3213,4987,1,8008,1,5385,4538,8867,2292,6285,858,7072,3593,5700,1,8778,1,4807,3812,7415,1,6449,1,9205,4197,4722,1421,7871,1890,4724,3217,8268,860,7043,728,7229,3289,4891,1953,9063,1545,4730,4205,7612,1,6392,1,8464,3787,4734,1,8154,558,5683,3650,9436,1,6317,2275,7211,4733,5417,1,8770,500,5173,3271,7114,2169,6883,180,8896,3164,5768,1,8024,864,4849,4432,8310,1,6333,1417,7715,3168,4752,775,9351,1902,5530,3170,7132,258,6658,1,8365,4380,4829,2077,7992,308,4760,3341,9062,1,6901,108,7144,3938,5197,1362,8735,734,5719,4590,7150,1,6584,1908,9388,3486,5021,1,8269,1411,5139,3182,8352,1993,6408,1,7534,4245,5922,1,9155,234,5059,3927,7168,504,7140,949,8605,3188,5465,132,7971,1914,4784,4253,9293,1368,6729,564,7180,3192,4788,2299,8931,158,4790,3297,7665,939,6389,1407,8986,4687,4794,1,8038,224,5892,3337,8503,182,6971,2021,7198,3657,4800,332,9556,1,4802,4366,7603,2035,6405,740,8408,3204,5798,1374,8367,1,5268,3847,9016,164,6642,1,7734,4277,5095,1,8823,2399,4814,3210,7305,1,7063,1,9375,3478,4818,1975,8104,420,4899,4778,8677,312,6429,1,7234,3859,5566,878,9314,1,5984,3218,7367,1577,6437,1932,8521,4330,5269,744,8235,1,4832,3222,9514,1934,7161,1382,7252,3517,5803,510,8898,570,5529,4559,7317,1,6453,1,9208,3689,4945,422,8340,2087,5011,3230,8651,1,6803,882,7270,4668,4979,2217,9495,1,5223,3295,7858,110,7096,314,8492,3883,5065,572,8091,1461,5827,4400,9106,884,6477,2011,7635,3319,4973,1,9111,1,4862,3705,7532,2335,6485,138,9710,4372,5978,264,8111,1,5025,3954,8520,1499,7034,1,7793,3439,4872,1,9368,1950,5317,4713,7312,1,6904,1593,8587,3252,4878,1952,8402,888,5618,3254,9517,228,6509,752,7324,4589,5141,1,8992,1,5863,3258,7679,338,7241,2370,9213,3260,4890,1525,8314,1,4965,4349,8562,2061,6758,1,7342,3515,5964,1,9708,1400,4981,3919,7427,102,6604,240,8877,4852,5308,1,8214,2015,4904,3737,9196,578,7195,1,7583,3272,5609,2115,8999,1,4910,4365,7857,1465,6549,941,9518,4062,5220,318,8568,1,5899,3391,8604,1,6706,2249,7378,4373,4920,1,9472,758,5662,3475,7491,2149,7112,230,8618,3820,6108,1,8211,168,5307,4819,9791,1,6626,1,7918,3461,4932,1410,9180,1974,4934,3612,7402,140,6957,1,9256,4389,4938,2450,8231,1495,5389,3383,8912,242,7382,1,7767,3955,4944,1,9683,931,5978,4554,7420,762,6694,1980,8660,3300,5758,522,8592,1,4952,3302,9286,2265,6732,1,7432,4772,5947,955,9146,432,4958,3967,7505,212,7193,1527,9797,3308,5454,1,8271,2383,5673,4413,8761,1,6952,1,7641,3828,4968,1988,9615,524,4970,3314,8024,1,6629,164,8815,4659,4974,1654,8291,1,6170,3425,9642,270,7269,2173,7599,3320,5363,434,9214,1424,5275,4962,7527,1994,6796,1,9435,3324,5983,827,8588,1,4988,4143,8773,908,6653,588,7985,4437,5736,150,9959,1998,4994,3330,7719,1428,7438,104,8744,3332,5261,2000,8467,770,5000,4546,9531 };

LL N;
LL ans = 0LL;
vector<LL> divisor(LL n) {
	vector<LL> res;
	for (LL i = 2; i*i <= n; i++) {
		if (n%i == 0) {
			res.push_back(i);
			n /= i;
			while (n%i == 0)n /= i;
		}
	}
	if (n != 1)res.push_back(n);
	return res;
}

#define primeN 12000000 
LL  val[primeN + 1];

void  make_val() {// N log N
	FOR(i, 0, primeN + 1) {
		val[i] = 1;
	}val[0] = val[1] = 0;

	for (LL i = 2; i <= primeN; i++) {
		for (LL j = i * 2; j <= primeN; j += i)
			val[j] = max(val[j], val[i] * (j / i) + 1LL);
	}
}

map<LL, LL>Map;
LL f(LL n) {
	if (n < 10001)return memo[n];
	if (Map[n] != 0)return Map[n];
	LL res = 1;
	VL div = divisor(n);
	FOR(i, 0, SZ(div)) {
		if (div[i] == n)continue;
		res = max(res, f(div[i])*(n / div[i]) + 1);
		res = max(res, f(n/div[i])*(div[i]) + 1);
	}

	return Map[n] = res;
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	//cin >> N;
	//VI a = divisor(N);
	//SORT(a);
	//UNIQ(a);
	//FOR(i, 0, SZ(a)) {
	//	if (a[i] != N)cout << "a[i]:" << a[i] << ", val" << N / a[i] * memo[a[i]] + 1 << endl;
	//}

	//make_val();
	//FOR(i, 10000, primeN) {
	//	LL num = f(i);
	//	if (num != val[i]) {
	//		cout << i << endl;
	//		VL vl = divisor(i);
	//		FOR(i, 0, SZ(vl)) {
	//			cout << vl[i] << " ";
	//		}cout << endl;
	//		return 0;
	//	}
	//	assert(num == val[i]);
	//}
	cin >> N;
	VL x(N);
	FOR(i, 0, N) {
		cin >> x[i];
		ans += x[i];
		ans += f(x[i]);
		/*if (x[i] <= primeN)ans += val[x[i]];
		else assert(0);*/
	}
	cout << ans << "\n";

	return 0;
}