#include <bits/stdc++.h>

using namespace std;

vector<int> vec = {0,0,0,2,0,0,2,3,0,7,0,5,2,3,3,8,0,5,7,8,0,17,5,9,2,6,3,21,3,9,8,12,0,26,5,15,7,12,8,23,0,14,17,17,5,31,9,18,2,24,6,32,3,18,21,23,3,41,9,23,8,21,12,58,0,18,26,26,5,47,15,27,7,26,12,44,8,44,23,30,0,62,14,32,17,26,17,53,5,32,31,42,9,62,18,38,2,35,24,86,6,36,32,39,3,83,18,41,21,39,23,68,3,41,41,45,9,82,23,56,8,55,21,77,12,42,58,48,0,86,18,50,26,71,26,99,5,50,47,53,15,92,27,62,7,48,26,122,12,54,44,57,8,110,44,60,23,57,30,98,0,84,62,62,14,122,32,63,17,60,26,137,17,63,53,81,5,116,32,68,31,66,42,113,9,63,62,83,18,180,38,72,2,71,35,116,24,72,86,75,6,131,36,96,32,71,39,160,3,104,83,80,18,137,41,83,21,111,39,137,23,77,68,84,3,157,41,86,41,84,45,221,9,86,82,90,23,152,56,90,8,89,55,184,21,120,77,101,12,161,42,95,58,122,48,155,0,95,86,123,18,184,50,99,26,93,71,167,26,99,99,102,5,218,50,119,47,102,53,211,15,104,92,107,27,197,62,137,7,106,48,182,26,108,122,113,12,263,54,120,44,152,57,188,8,108,110,116,44,197,60,117,23,116,57,286,30,117,98,140,0,206,84,134,62,111,62,203,14,165,122,125,32,235,63,128,17,125,60,212,26,161,137,171,17,233,63,131,53,129,81,258,5,131,116,135,32,287,68,135,31,151,66,275,42,131,113,138,9,263,63,177,62,138,83,230,18,135,180,143,38,242,72,144,2,218,71,290,35,144,116,158,24,251,72,150,86,147,75,356,6,149,131,159,36,302,96,179,32,152,71,257,39,206,160,158,3,266,104,158,83,156,80,313,18,149,137,204,41,317,83,162,21,161,111,266,39,197,137,165,23,415,77,167,68,161,84,278,3,167,157,200,41,287,86,213,41,170,84,341,45,171,221,174,9,308,86,176,82,233,90,293,23,221,152,194,56,337,90,180,8,174,89,422,55,176,184,183,21,311,120,185,77,179,101,416,12,246,161,188,42,317,95,189,58,183,122,314,48,189,155,245,0,422,95,195,86,239,123,323,18,194,184,197,50,419,99,209,26,216,93,392,71,194,167,203,26,341,99,317,99,201,102,338,5,198,218,206,50,388,119,227,47,273,102,341,53,207,211,218,15,419,104,212,92,206,107,545,27,212,197,215,62,362,137,231,7,215,106,362,48,287,182,257,26,409,108,221,122,260,113,368,12,221,263,281,54,377,120,225,44,224,152,443,57,271,188,228,8,488,108,237,110,228,116,380,44,230,197,233,60,498,117,299,23,228,116,518,57,230,286,237,30,401,117,240,98,315,140,466,0,239,206,242,84,422,134,243,62,299,111,557,62,243,203,248,14,467,165,248,122,246,125,410,32,353,235,270,63,422,128,296,17,251,125,495,60,252,212,326,26,431,161,257,137,251,171,428,17,252,233,260,63,749,131,263,53,257,129,437,81,261,258,290,5,458,131,339,116,264,135,517,32,309,287,311,68,452,135,270,31,354,151,452,66,261,275,273,42,549,131,287,113,273,138,608,9,338,263,278,63,512,177,279,62,273,138,545,83,368,230,282,18,476,135,285,180,282,143,611,38,284,242,366,72,539,144,296,2,287,218,482,71,288,290,306,35,623,144,323,116,356,158,576,24,288,251,296,72,497,150,380,86,291,147,491,75,297,356,311,6,569,149,356,131,420,159,503,36,302,302,305,96,512,179,308,32,356,152,745,71,306,257,309,39,608,206,311,160,309,158,518,3,413,266,315,104,657,158,315,83,312,156,527,80,306,313,490,18,536,149,345,137,318,204,671,41,320,317,323,83,692,162,324,21,318,161,542,111,395,266,335,39,620,197,417,137,327,165,548,23,329,415,332,77,572,167,333,68,435,161,791,84,386,278,338,3,608,167,357,157,332,200,761,41,333,287,341,86,643,213,342,41,416,170,566,84,449,341,345,45,581,171,354,221,336,174,670,9,347,308,512,86,587,176,410,82,350,233,587,90,351,293,383,23,894,221,356,152,350,194,593,56,356,337,360,90,707,180,461,8,384,174,698,89,356,422,363,55,674,176,365,184,476,183,599,21,365,311,434,120,694,185,369,77,363,179,827,101,422,416,372,12,626,246,375,161,372,188,735,42,569,317,389,95,647,189,416,58,377,183,632,122,378,314,483,48,722,189,383,155,381,245,806,0,374,422,393,95,857,195,387,86,386,239,796,123,383,323,390,18,656,194,501,184,512,197,653,50,392,419,395,99,785,209,398,26,516,216,662,93,396,392,399,71,683,194,473,167,399,203,977,26,396,341,419,99,677,317,413,99,459,201,755,102,555,338,408,5,930,198,410,218,408,206,680,50,410,388,528,119,692,227,414,47,395,273,818,102,414,341,491,53,893,207,420,211,417,218,698,15,482,419,422,104,793,212,609,92,422,206,701,107,512,545,428,27,716,212,440,197,557,215,823,62,423,362,456,137,722,231,432,7,431,215,1097,106,428,362,479,48,899,287,437,182,431,257,728,26,570,409,440,108,797,221,456,122,533,260,851,113,441,368,567,12,758,221,446,263,440,281,743,54,446,377,450,120,1208,225,530,44,449,224,752,152,446,443,464,57,803,271,582,188,453,228,910,8,455,488,495,108,902,237,459,110,606,228,767,116,459,380,462,44,875,230,506,197,462,233,1031,60,461,498,551,117,797,299,488,23,467,228,902,116,611,518,473,57,791,230,473,286,467,237,788,30,608,401,609,117,975,240,506,98,545,315,788,140,477,466,480,0,1028,239,482,206,476,242,1079,84,482,422,485,134,812,243,618,62,485,299,812,111,486,557,489,62,919,243,491,203,746,248,986,14,486,467,495,165,827,248,495,122,494,246,1293,125,486,410,498,32,836,353,600,235,557,270,830,63,651,422,510,128,949,296,515,17,498,251,842,125,575,495,650,60,1004,252,510,212,572,326,976,26,509,431,531,161,1091,257,513,137,510,251,857,171,513,428,605,17,1031,252,663,233,516,260,863,63,513,749,575,131,872,263,530,53,678,257,1051,129,629,437,525,81,881,261,570,258,521,290,1166,5,527,458,542,131,1000,339,533,116,525,264,1103,135,705,517,534,32,983,309,536,287,534,311,1053,68,536,452,686,135,902,270,540,31,650,354,896,151,532,452,543,66,1435,261,545,275,543,273,905,42,606,549,548,131,917,287,923,113,543,273,1055,138,545,608,552,9,926,338,569,263,719,278,920,63,554,512,557,177,1295,279,558,62,557,273,1232,138,558,545,603,83,941,368,563,230,638,282,1078,18,758,476,668,135,947,285,567,180,563,282,941,143,563,611,804,38,1075,284,572,242,561,366,953,72,689,539,575,144,1232,296,578,2,570,287,1274,218,647,482,579,71,983,288,740,290,579,306,1196,35,581,623,585,144,1102,323,585,116,759,356,977,158,581,576,588,24,986,288,590,251,706,296,1432,72,671,497,593,150,1052,380,594,86,588,291,1082,147,773,491,623,75,1217,297,701,356,597,311,995,6,599,569,771,149,1022,356,603,131,602,420,1157,159,603,503,665,36,1586,302,608,302,606,305,1013,96,594,512,611,179,1153,308,785,32,684,356,1016,152,612,745,725,71,1031,306,654,257,825,309,1212,39,614,608,627,206,1142,311,623,160,620,309,1367,158,746,518,624,3,1174,413,626,266,624,315,1043,104,813,657,644,158,1097,315,683,83,628,312,1418,156,626,527,812,80,1061,306,701,313,633,490,1055,18,635,536,638,149,1639,345,647,137,803,318,1067,204,639,671,662,41,1076,320,855,317,638,323,1231,83,644,692,647,162,1169,324,764,21,920,318,1082,161,648,542,653,111,1232,395,678,266,651,335,1436,39,648,620,656,197,1292,417,668,137,656,327,1287,165,854,548,660,23,1106,329,692,415,656,332,1301,77,657,572,1097,167,1255,333,681,68,665,435,1112,161,662,791,669,84,1430,386,671,278,669,338,1282,3,806,608,675,167,1127,357,866,157,674,332,1127,200,751,761,686,41,1376,333,680,287,900,341,1361,86,759,643,695,213,1142,342,684,41,674,416,1663,170,755,566,687,84,1193,449,690,341,824,345,1148,45,894,581,764,171,1304,354,693,221,727,336,1157,174,689,670,888,9,1166,347,821,308,696,512,1511,86,693,587,701,176,1502,410,702,82,701,350,1166,233,702,587,705,90,1751,351,906,293,687,383,1175,23,707,894,753,221,1187,356,713,152,921,350,1361,194,711,593,842,56,1208,356,716,337,797,360,1583,90,716,707,720,180,1452,461,794,8,716,384,1202,174,1094,698,752,89,1211,356,725,422,723,363,1436,55,720,674,933,176,1217,365,749,184,723,476,1493,183,729,599,732,21,1894,365,791,311,827,434,1223,120,729,694,744,185,1247,369,947,77,884,363,1454,179,738,827,756,101,1241,422,743,416,962,372,1238,12,738,626,746,246,1406,375,881,161,746,372,1772,188,747,735,750,42,1358,569,752,317,746,389,1435,95,998,647,755,189,1487,416,798,58,755,377,1262,183,827,632,973,122,1508,378,761,314,759,483,1268,48,860,722,896,189,1637,383,765,155,759,381,1463,245,761,806,833,0,1286,374,987,422,768,393,1280,95,926,857,792,195,1459,387,774,86,1028,386,1286,239,774,796,857,123,1301,383,794,323,854,390,2330,18,779,656,782,194,1322,501,783,184,782,512,1307,197,1095,653,788,50,1487,392,788,419,941,395,1313,99,783,785,1097,209,1457,398,792,26,791,516,1561,216,788,662,803,93,1703,396,941,392,782,399,1328,71,797,683,800,194,1611,473,1023,167,800,399,1547,203,801,977,804,26,1580,396,890,341,1043,419,1537,99,806,677,810,317,1352,413,821,99,809,459,1772,201,806,755,959,102,1538,555,822,338,809,408,1349,5,1056,930,818,198,1367,410,845,218,983,408,1643,206,980,680,1055,50,1439,410,825,388,819,528,1373,119,903,692,827,227,2071,414,828,47,864,395,1688,273,828,818,833,102,1391,414,1068,341,831,491,1742,53,824,893,848,207,1397,420,908,211,1271,417,1391,218,837,698,840,15,1694,482,842,419,836,422,1841,104,837,793,845,212,1412,609,995,92,840,422,1616,206,1205,701,902,107,1433,512,851,545,849,428,1418,27,851,716,1086,212,2075,440,893,197,854,557,1427,215,851,823,858,62,1838,423,879,362,858,456,1688,137,860,722,1145,231,1487,432,1194,7,858,431,1442,215,864,1097,867,106,1640,428,870,362,1124,479,1448,48,1040,899,945,287,1544,437,881,182,869,431,2122,257,873,728,878,26,1619,570,878,409,876,440,1781,108,1163,797,881,221,1751,456,882,122,876,533,1466,260,882,851,1136,113,1481,441,899,368,1097,567,1690,12,984,758,890,221,1907,446,980,263,890,440,1481,281,891,743,894,54,1684,446,1448,377,894,450,1493,120,896,1208,900,225,1562,530,900,44,1200,449,1772,224,882,752,923,152,1784,446,905,443,1016,464,2108,57,905,803,938,271,1714,582,909,188,899,453,1517,228,1178,910,1073,8,1526,455,915,488,912,495,1741,108,914,902,1176,237,1547,459,918,110,1002,606,1778,228,1097,767,923,116,2325,459,923,380,1022,462,1538,44,905,875,926,230,1547,506,1190,197,926,462,2072,233,927,1031,956,60,1556,461,939,498,1230,551,1553,117,1049,797,972,299,1765,488,938,23,1118,467,2072,228,932,902,939,116,1583,611,1020,518,935,473,1994,57,1218,791,945,230,1577,473,1115,286,944,467,1574,237,936,788,1354,30,1793,608,950,401,944,609,1574,117,1031,975,953,240,2450,506,954,98,948,545,1820,315,954,788,957,140,1733,477,1226,466,957,480,1598,0,954,1028,1136,239,2090,482,974,206,1245,476,1607,242,1052,1079,981,84,1616,482,968,422,962,485,2354,134,1193,812,978,243,1622,618,972,62,971,485,1616,299,1290,812,1058,111,1845,486,1079,557,971,489,1976,62,977,919,1257,243,1682,491,983,203,980,746,1931,248,981,986,1028,14,2105,486,1011,467,1175,495,1643,165,986,827,1046,248,1867,495,1266,122,1112,494,1652,246,1080,1293,993,125,1661,486,1175,410,1286,498,1946,32,995,836,998,353,1667,600,999,235,980,557,2177,270,995,830,1002,63,2372,651,1019,422,1002,510,1931,128,1299,949,1007,296,1697,515,1008,17,1007,498,2071,251,1008,842,1583,125,1793,575,1013,495,1007,650,1685,60,1008,1004,1016,252,2585,510,1017,212,1016,572,1691,326,1331,976,1020,26,1706,509,1311,431,1011,531,2007,161,1022,1091,1025,257,1712,513,1028,137,1433,510,2078,251,1026,857,1037,171,1939,513,1061,428,1029,605,2246,17,1031,1031,1136,252,1727,663,1100,233,1235,516,1973,260,1365,863,1038,63,1778,513,1052,749,1121,575,1724,131,1040,872,1338,263,2088,530,1360,53,1038,678,1742,257,1044,1051,1047,129,2561,629,1091,437,1047,525,1996,81,1049,881,1052,261,2072,570,1352,258,1050,521,1757,290,1049,1166,1058,5,1997,527,1058,458,1446,542,1763,131,1049,1000,1253,339,1922,533,1172,116,1061,525,2717,264,1062,1103,1076,135,1781,705,1067,517,1061,534,1775,32,1622,983,1070,309,2020,536,1073,287,1070,534,1787,311,1071,1053,1379,68,1808,536,1119,452,1205,686,2405,135,1067,902,1167,270,2312,540,1080,31,1166,650,1922,354,1076,896,1083,151,2171,532,1487,452,1292,543,1805,66,1085,1435,1095,261,1817,545,1089,275,1433,543,2285,273,1089,905,1121,42,1826,606,1286,549,1092,548,2381,131,1209,917,1122,287,2062,923,1098,113,1092,543,1832,273,1421,1055,1103,138,2174,545,1103,608,1097,552,2166,9,1298,926,1419,338,1847,569,1115,263,1106,719,1841,278,1107,920,1310,63,2812,554,1112,512,1106,557,2111,177,1112,1295,1115,279,1862,558,1424,62,1110,557,2126,273,1331,1232,1235,138,1883,558,1140,545,1485,603,1868,83,1118,941,1125,368,2234,563,1125,230,1124,638,2852,282,1121,1078,1199,18,1949,758,1130,476,1247,668,2201,135,1461,947,1133,285,2087,567,1134,180,1357,563,1892,282,1130,941,1460,143,2150,563,1140,611,1137,804,1898,38,1139,1075,1154,284,2441,572,1349,242,1142,561,2249,366,1232,953,1188,72,1916,689,1772,539,1146,575,1913,144,1143,1232,1151,296,2738,578,1178,2,1488,570,1913,287,1148,1274,1155,218,1973,647,1157,482,1151,579,2914,71,1157,983,1370,288,1937,740,1163,290,1301,579,1937,306,1502,1196,1184,35,2484,581,1173,623,1164,585,1940,144,1391,1102,1496,323,1952,585,1170,116,1169,759,2228,356,1164,977,1211,158,2513,581,1248,576,1169,588,2564,24,1175,986,1232,288,2224,590,1514,251,1160,706,1967,296,1268,1432,1283,72,1976,671,1185,497,1799,593,2365,150,1179,1052,1187,380,1997,594,1188,86,1187,588,2582,291,1331,1082,1206,147,2252,773,1409,491,1191,623,1988,75,1578,1217,1196,297,1997,701,1197,356,1299,597,2326,311,1322,995,1541,6,2369,599,1202,569,1196,771,2003,149,1202,1022,1328,356,3044,603,1208,131,1205,602,2006,420,1206,1157,1427,159,2108,603,1554,503,1209,665,2302,36,1206,1586,1215,302,2072,608,1244,302,1569,606,2297,305,1487,1013,1229,96,2562,594,1220,512,1218,611,2783,179,1220,1153,1223,308,2042,785,1232,32,1218,684,2890,356,1583,1016,1227,152,2051,612,1244,745,1223,725,2048,71,1226,1031,1682,306,2324,654,1361,257,1583,825,2057,309,1229,1212,1238,39,2648,614,1238,608,1236,627,2353,206,1233,1142,1241,311,2072,623,1976,160,1241,620,2054,309,1349,1367,1245,158,2480,746,1247,518,1769,624,2078,3,1247,1174,1250,413,2462,626,1353,266,1341,624,3040,315,1247,1043,1254,104,2108,813,1256,657,1250,644,2093,158,1623,1097,1481,315,2377,683,1260,83,1259,628,2408,312,1256,1418,1617,156,2111,626,1265,527,1263,812,2481,80,1508,1061,1347,306,3047,701,1280,313,1263,633,2117,490,1269,1055,1272,18,2398,635,1631,536,1367,638,2561,149,1427,1639,1307,345,2147,647,1278,137,1650,803,2432,318,1278,1067,1283,204,2204,639,1290,671,1526,662,2786,41,1274,1076,1395,320,2565,855,1340,317,1286,638,2141,323,1664,1231,1424,83,2288,644,1526,692,1272,647,2455,162,1292,1169,1658,324,2162,764,1298,21,1295,920,2162,318,1296,1082,1299,161,3731,648,1301,542,1299,653,2165,111,1434,1232,1319,395,2402,678,1779,266,1351,651,2723,335,1289,1436,1544,39,2186,648,1310,620,1691,656,2180,197,1305,1292,1313,417,2479,668,1397,137,1308,656,2852,327,1576,1287,1317,165,2201,854,1451,548,1317,660,2711,23,1704,1106,1329,329,2294,692,1323,415,1322,656,2663,332,1323,1301,1698,77,2648,657,1328,572,1326,1097,2213,167,1323,1255,1331,333,2849,681,1370,68,1745,665,2581,435,1332,1112,1335,161,2231,662,1716,791,1545,669,2225,84,1436,1430,1340,386,2530,671,1574,278,1778,669,2237,338,1341,1282,1344,3,2258,806,1358,608,1340,675,3761,167,1346,1127,1350,357,2657,866,1394,157,1344,674,2252,332,1770,1127,1353,200,2558,751,1470,761,1353,686,2255,41,1355,1376,2150,333,2327,680,1359,287,1344,900,2734,341,1520,1361,1362,86,2918,759,1365,643,1362,695,2273,213,1625,1142,1367,342,2733,684,1757,41,1364,674,2282,416,1364,1663,1430,170,2483,755,1373,566,1772,687,3068,84,1368,1193,1520,449,2297,690,1377,341,1376,824,3044,345,1377,1148,1388,45,2609,894,1401,581,1682,764,2303,171,1892,1304,1385,354,2312,693,1388,221,1385,727,2726,336,1386,1157,1947,174,2555,689,1643,670,1389,888,2318,9,1488,1166,1395,347,3503,821,1395,308,1392,696,2327,512,1386,1511,1398,86,2759,693,1793,587,1398,701,2711,176,1395,1502,1403,410,2447,702,1550,82,1838,701,2342,350,1547,1166,1795,233,2807,702,1410,587,1399,705,3056,90,1409,1751,1449,351,2372,906,1413,293,1412,687,2687,383,2228,1175,1431,23,2366,707,1418,894,1583,753,2360,221,1413,1187,1824,356,2683,713,1433,152,1421,921,3047,350,1422,1361,1445,194,3053,711,1427,593,1421,842,2960,56,1422,1208,1455,356,2537,716,1833,337,1703,797,2723,360,1431,1583,1434,90,2702,716,1502,707,1853,720,2393,180,1436,1452,1481,461,2402,794,1700,8,1584,716,3499,384,1436,1202,1443,174,2411,1094,1445,698,1443,752,2405,89,2054,1211,1460,356,3362,725,1449,422,1443,723,2417,363,1445,1436,1974,55,2426,720,1542,674,1452,933,2761,176,1454,1217,1721,365,3116,749,1581,184,1457,723,2432,476,1454,1493,1610,183,2762,729,1878,599,1562,732,2438,21,1778,1894,1466,365,2447,791,1467,311,1973,827,2877,434,1467,1223,1470,120,2456,729,1472,694,1461,744,3734,185,1472,1247,1475,369,3350,947,1478,77,1596,884,2456,363,1907,1454,1479,179,2483,738,1481,827,1760,756,2812,101,1580,1241,1901,422,2477,743,1511,416,1481,962,2477,372,1467,1238,1488,12,3926,738,1958,626,1484,746,2474,246,1487,1406,1620,375,2492,881,1919,161,1488,746,2840,372,1494,1772,1505,188,2999,747,1556,735,1934,750,2786,42,1499,1358,1502,569,2834,752,1503,317,1679,746,3257,389,1503,1435,1775,95,2558,998,1508,647,1506,755,2961,189,2106,1487,1511,416,2582,798,1532,58,1506,755,2516,377,1799,1262,1946,183,2864,827,1524,632,1511,973,2876,122,1517,1508,1520,378,3257,761,1523,314,1520,759,3407,483,1646,1268,1535,48,2558,860,2072,722,1520,896,2861,189,1526,1637,1544,383,3042,765,1530,155,2324,759,2552,381,1772,1463,1577,245,2663,761,1535,806,1533,833,3724,0,1532,1286,1538,374,2567,987,1817,422,1533,768,2564,393,1988,1280,1542,95,2915,926,1545,857,1697,792,2573,195,1539,1459,2339,387,3044,774,1548,86,1547,1028,3098,386,1548,1286,1553,239,3323,774,1553,796,1547,857,2588,123,1548,1301,1832,383,2938,794,2000,323,1556,854,2591,390,1557,2330,1560,18,2879,779,1695,656,2066,782,2965,194,1859,1322,1637,501,2657,783,1581,184,1565,782,3392,512,1562,1307,1634,197,3279,1095,1608,653,1670,788,3146,50,2028,1487,1575,392,2627,788,1736,419,1574,941,2993,395,1566,1313,2027,99,2858,783,1580,785,1877,1097,2630,209,1580,1457,1583,398,3962,792,1613,26,1566,791,2642,516,1584,1561,1587,216,2714,788,2446,662,1772,803,3120,93,1589,1703,1592,396,2672,941,1694,392,2055,782,2651,399,1593,1328,1728,71,3740,797,1598,683,1596,800,3533,194,1593,1611,1613,473,2672,1023,1602,167,1601,800,3347,399,2148,1547,1895,203,2681,801,1607,977,1601,804,2678,26,1607,1580,2067,396,3200,890,1613,341,1610,1043,2687,419,2072,1537,1622,99,3455,806,1670,677,1745,810,3067,317,1805,1352,1620,413,2702,821,2081,99,1614,809,3248,459,1611,1772,1623,201,3061,806,1668,755,2096,959,2702,102,1625,1538,1628,555,2717,822,1703,338,1973,809,4473,408,1629,1349,1802,5,2726,1056,1676,930,1632,818,2723,198,2168,1367,1637,410,3089,845,1934,218,1634,983,3032,408,1638,1643,2103,206,2741,980,1662,680,1637,1055,3118,50,1638,1439,1676,410,4613,825,1647,388,1809,819,2741,528,1647,1373,1688,119,3284,903,2117,692,1646,827,2750,227,1652,2071,1955,414,2762,828,1658,47,2136,864,3146,395,1656,1688,1659,273,2858,828,1835,818,1772,833,3596,102,2090,1391,1665,414,3140,1068,1808,341,1664,831,2777,491,2175,1742,1668,53,2786,824,1670,893,1664,848,3929,207,1670,1397,2226,420,2792,908,1674,211,1928,1271,2792,417,1670,1391,1688,218,4189,837,1694,698,2011,840,2798,15,1679,1694,1682,482,3041,842,2162,419,1735,836,3197,422,1683,1841,1788,104,2816,837,1994,793,2177,845,3191,212,1670,1412,1691,609,3360,995,1700,92,1691,840,3797,422,1692,1616,1695,206,3344,1205,1697,701,1686,902,3220,107,2190,1433,1845,512,2837,851,1703,545,1695,849,2837,428,1898,1418,2678,27,3214,851,1706,716,1704,1086,2840,212,1701,2075,1710,440,4022,893,1781,197,1709,854,3357,557,2072,1427,1713,215,2861,851,2202,823,1709,858,2849,62,1884,1838,1898,423,3244,879,1719,362,2243,858,3443,456,1715,1688,1722,137,2876,860,1725,722,1722,1145,4190,231,1841,1487,1727,432,2897,1194,1739,7,2054,858,2876,431,2231,1442,1773,215,3827,864,1842,1097,1731,867,3236,106,1719,1640,2229,428,2897,870,2051,362,1733,1124,3346,479,1737,1448,1740,48,3725,1040,1742,899,1736,945,2903,287,1742,1544,1745,437,4064,881,2558,182,1745,869,2912,431,1853,2122,1749,257,2933,873,1758,728,2445,878,3438,26,1751,1619,2063,570,2927,878,1755,409,1893,876,3797,440,1751,1781,1838,108,3323,1163,1760,797,1954,881,2930,221,2675,1751,1788,456,2942,882,1764,122,1758,876,3350,533,1760,1466,2270,260,2951,882,1916,851,1763,1136,3536,113,1769,1481,1772,441,4470,899,1793,368,1772,1097,3353,567,1773,1690,1778,12,2966,984,2283,758,2111,890,3578,221,1760,1907,1854,446,2972,980,1782,263,2363,890,2966,440,1889,1481,1785,281,3679,891,2111,743,1781,894,3866,54,1994,1684,1797,446,3122,1448,1806,377,1787,894,3689,450,2312,1493,1794,120,3530,896,1796,1208,1794,900,2993,225,1796,1562,2306,530,3395,900,1800,44,1799,1200,3002,449,1920,1772,2561,224,3863,882,1817,752,1803,923,3476,152,1805,1784,1851,446,3017,905,2319,443,1799,1016,3017,464,2150,2108,1812,57,3602,905,1815,803,2339,938,3023,271,1929,1714,1836,582,3347,909,1844,188,1812,899,5390,453,1997,1517,1823,228,3041,1178,1907,910,1821,1073,3038,8,2378,1526,1941,455,3448,915,1827,488,2171,912,3032,495,1827,1741,2348,108,3056,914,2024,902,1826,1176,3597,237,1832,1547,1889,459,3932,918,2165,110,1946,1002,3422,606,1827,1778,1839,228,3469,1097,2364,767,1839,923,3068,116,1839,2325,1845,459,3632,923,1845,380,2621,1022,3503,462,1836,1538,1856,44,3278,905,1850,875,1848,926,4133,230,1850,1547,2189,506,3683,1190,1854,197,2108,926,3092,462,2460,2072,1857,233,3143,927,1860,1031,1857,956,3884,60,2231,1556,2391,461,3122,939,1863,498,1862,1230,3107,551,1863,1553,1881,117,4648,1049,1875,797,1862,972,3731,299,1863,1765,1871,488,3122,938,2784,23,1871,1118,3672,467,2087,2072,1875,228};

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

    int n;
    cin >> n;

    int res = 0;
    for (int i=0; i<=n; i++) res += vec[i];

    cout << res << "\n";
}