#include <cstdio>
#include <cstdlib>

#include <utility>

static const std::pair<int, int> PRECOMPUTED[] = {{3,2},{6,2},{7,3},{9,7},{11,5},{12,2},{13,3},{14,3},{15,8},{17,5},{18,7},{19,8},{21,17},{22,5},{23,9},{24,2},{25,6},{26,3},{27,21},{28,3},{29,9},{30,8},{31,12},{33,26},{34,5},{35,15},{36,7},{37,12},{38,8},{39,23},{41,14},{42,17},{43,17},{44,5},{45,31},{46,9},{47,18},{48,2},{49,24},{50,6},{51,32},{52,3},{53,18},{54,21},{55,23},{56,3},{57,41},{58,9},{59,23},{60,8},{61,21},{62,12},{63,58},{65,18},{66,26},{67,26},{68,5},{69,47},{70,15},{71,27},{72,7},{73,26},{74,12},{75,44},{76,8},{77,44},{78,23},{79,30},{81,62},{82,14},{83,32},{84,17},{85,26},{86,17},{87,53},{88,5},{89,32},{90,31},{91,42},{92,9},{93,62},{94,18},{95,38},{96,2},{97,35},{98,24},{99,86},{100,6},{101,36},{102,32},{103,39},{104,3},{105,83},{106,18},{107,41},{108,21},{109,39},{110,23},{111,68},{112,3},{113,41},{114,41},{115,45},{116,9},{117,82},{118,23},{119,56},{120,8},{121,55},{122,21},{123,77},{124,12},{125,42},{126,58},{127,48},{129,86},{130,18},{131,50},{132,26},{133,71},{134,26},{135,99},{136,5},{137,50},{138,47},{139,53},{140,15},{141,92},{142,27},{143,62},{144,7},{145,48},{146,26},{147,122},{148,12},{149,54},{150,44},{151,57},{152,8},{153,110},{154,44},{155,60},{156,23},{157,57},{158,30},{159,98},{161,84},{162,62},{163,62},{164,14},{165,122},{166,32},{167,63},{168,17},{169,60},{170,26},{171,137},{172,17},{173,63},{174,53},{175,81},{176,5},{177,116},{178,32},{179,68},{180,31},{181,66},{182,42},{183,113},{184,9},{185,63},{186,62},{187,83},{188,18},{189,180},{190,38},{191,72},{192,2},{193,71},{194,35},{195,116},{196,24},{197,72},{198,86},{199,75},{200,6},{201,131},{202,36},{203,96},{204,32},{205,71},{206,39},{207,160},{208,3},{209,104},{210,83},{211,80},{212,18},{213,137},{214,41},{215,83},{216,21},{217,111},{218,39},{219,137},{220,23},{221,77},{222,68},{223,84},{224,3},{225,157},{226,41},{227,86},{228,41},{229,84},{230,45},{231,221},{232,9},{233,86},{234,82},{235,90},{236,23},{237,152},{238,56},{239,90},{240,8},{241,89},{242,55},{243,184},{244,21},{245,120},{246,77},{247,101},{248,12},{249,161},{250,42},{251,95},{252,58},{253,122},{254,48},{255,155},{257,95},{258,86},{259,123},{260,18},{261,184},{262,50},{263,99},{264,26},{265,93},{266,71},{267,167},{268,26},{269,99},{270,99},{271,102},{272,5},{273,218},{274,50},{275,119},{276,47},{277,102},{278,53},{279,211},{280,15},{281,104},{282,92},{283,107},{284,27},{285,197},{286,62},{287,137},{288,7},{289,106},{290,48},{291,182},{292,26},{293,108},{294,122},{295,113},{296,12},{297,263},{298,54},{299,120},{300,44},{301,152},{302,57},{303,188},{304,8},{305,108},{306,110},{307,116},{308,44},{309,197},{310,60},{311,117},{312,23},{313,116},{314,57},{315,286},{316,30},{317,117},{318,98},{319,140},{321,206},{322,84},{323,134},{324,62},{325,111},{326,62},{327,203},{328,14},{329,165},{330,122},{331,125},{332,32},{333,235},{334,63},{335,128},{336,17},{337,125},{338,60},{339,212},{340,26},{341,161},{342,137},{343,171},{344,17},{345,233},{346,63},{347,131},{348,53},{349,129},{350,81},{351,258},{352,5},{353,131},{354,116},{355,135},{356,32},{357,287},{358,68},{359,135},{360,31},{361,151},{362,66},{363,275},{364,42},{365,131},{366,113},{367,138},{368,9},{369,263},{370,63},{371,177},{372,62},{373,138},{374,83},{375,230},{376,18},{377,135},{378,180},{379,143},{380,38},{381,242},{382,72},{383,144},{384,2},{385,218},{386,71},{387,290},{388,35},{389,144},{390,116},{391,158},{392,24},{393,251},{394,72},{395,150},{396,86},{397,147},{398,75},{399,356},{400,6},{401,149},{402,131},{403,159},{404,36},{405,302},{406,96},{407,179},{408,32},{409,152},{410,71},{411,257},{412,39},{413,206},{414,160},{415,158},{416,3},{417,266},{418,104},{419,158},{420,83},{421,156},{422,80},{423,313},{424,18},{425,149},{426,137},{427,204},{428,41},{429,317},{430,83},{431,162},{432,21},{433,161},{434,111},{435,266},{436,39},{437,197},{438,137},{439,165},{440,23},{441,415},{442,77},{443,167},{444,68},{445,161},{446,84},{447,278},{448,3},{449,167},{450,157},{451,200},{452,41},{453,287},{454,86},{455,213},{456,41},{457,170},{458,84},{459,341},{460,45},{461,171},{462,221},{463,174},{464,9},{465,308},{466,86},{467,176},{468,82},{469,233},{470,90},{471,293},{472,23},{473,221},{474,152},{475,194},{476,56},{477,337},{478,90},{479,180},{480,8},{481,174},{482,89},{483,422},{484,55},{485,176},{486,184},{487,183},{488,21},{489,311},{490,120},{491,185},{492,77},{493,179},{494,101},{495,416},{496,12},{497,246},{498,161},{499,188},{500,42},{501,317},{502,95},{503,189},{504,58},{505,183},{506,122},{507,314},{508,48},{509,189},{510,155},{511,245},{513,422},{514,95},{515,195},{516,86},{517,239},{518,123},{519,323},{520,18},{521,194},{522,184},{523,197},{524,50},{525,419},{526,99},{527,209},{528,26},{529,216},{530,93},{531,392},{532,71},{533,194},{534,167},{535,203},{536,26},{537,341},{538,99},{539,317},{540,99},{541,201},{542,102},{543,338},{544,5},{545,198},{546,218},{547,206},{548,50},{549,388},{550,119},{551,227},{552,47},{553,273},{554,102},{555,341},{556,53},{557,207},{558,211},{559,218},{560,15},{561,419},{562,104},{563,212},{564,92},{565,206},{566,107},{567,545},{568,27},{569,212},{570,197},{571,215},{572,62},{573,362},{574,137},{575,231},{576,7},{577,215},{578,106},{579,362},{580,48},{581,287},{582,182},{583,257},{584,26},{585,409},{586,108},{587,221},{588,122},{589,260},{590,113},{591,368},{592,12},{593,221},{594,263},{595,281},{596,54},{597,377},{598,120},{599,225},{600,44},{601,224},{602,152},{603,443},{604,57},{605,271},{606,188},{607,228},{608,8},{609,488},{610,108},{611,237},{612,110},{613,228},{614,116},{615,380},{616,44},{617,230},{618,197},{619,233},{620,60},{621,498},{622,117},{623,299},{624,23},{625,228},{626,116},{627,518},{628,57},{629,230},{630,286},{631,237},{632,30},{633,401},{634,117},{635,240},{636,98},{637,315},{638,140},{639,466},{641,239},{642,206},{643,242},{644,84},{645,422},{646,134},{647,243},{648,62},{649,299},{650,111},{651,557},{652,62},{653,243},{654,203},{655,248},{656,14},{657,467},{658,165},{659,248},{660,122},{661,246},{662,125},{663,410},{664,32},{665,353},{666,235},{667,270},{668,63},{669,422},{670,128},{671,296},{672,17},{673,251},{674,125},{675,495},{676,60},{677,252},{678,212},{679,326},{680,26},{681,431},{682,161},{683,257},{684,137},{685,251},{686,171},{687,428},{688,17},{689,252},{690,233},{691,260},{692,63},{693,749},{694,131},{695,263},{696,53},{697,257},{698,129},{699,437},{700,81},{701,261},{702,258},{703,290},{704,5},{705,458},{706,131},{707,339},{708,116},{709,264},{710,135},{711,517},{712,32},{713,309},{714,287},{715,311},{716,68},{717,452},{718,135},{719,270},{720,31},{721,354},{722,151},{723,452},{724,66},{725,261},{726,275},{727,273},{728,42},{729,549},{730,131},{731,287},{732,113},{733,273},{734,138},{735,608},{736,9},{737,338},{738,263},{739,278},{740,63},{741,512},{742,177},{743,279},{744,62},{745,273},{746,138},{747,545},{748,83},{749,368},{750,230},{751,282},{752,18},{753,476},{754,135},{755,285},{756,180},{757,282},{758,143},{759,611},{760,38},{761,284},{762,242},{763,366},{764,72},{765,539},{766,144},{767,296},{768,2},{769,287},{770,218},{771,482},{772,71},{773,288},{774,290},{775,306},{776,35},{777,623},{778,144},{779,323},{780,116},{781,356},{782,158},{783,576},{784,24},{785,288},{786,251},{787,296},{788,72},{789,497},{790,150},{791,380},{792,86},{793,291},{794,147},{795,491},{796,75},{797,297},{798,356},{799,311},{800,6},{801,569},{802,149},{803,356},{804,131},{805,420},{806,159},{807,503},{808,36},{809,302},{810,302},{811,305},{812,96},{813,512},{814,179},{815,308},{816,32},{817,356},{818,152},{819,745},{820,71},{821,306},{822,257},{823,309},{824,39},{825,608},{826,206},{827,311},{828,160},{829,309},{830,158},{831,518},{832,3},{833,413},{834,266},{835,315},{836,104},{837,657},{838,158},{839,315},{840,83},{841,312},{842,156},{843,527},{844,80},{845,306},{846,313},{847,490},{848,18},{849,536},{850,149},{851,345},{852,137},{853,318},{854,204},{855,671},{856,41},{857,320},{858,317},{859,323},{860,83},{861,692},{862,162},{863,324},{864,21},{865,318},{866,161},{867,542},{868,111},{869,395},{870,266},{871,335},{872,39},{873,620},{874,197},{875,417},{876,137},{877,327},{878,165},{879,548},{880,23},{881,329},{882,415},{883,332},{884,77},{885,572},{886,167},{887,333},{888,68},{889,435},{890,161},{891,791},{892,84},{893,386},{894,278},{895,338},{896,3},{897,608},{898,167},{899,357},{900,157},{901,332},{902,200},{903,761},{904,41},{905,333},{906,287},{907,341},{908,86},{909,643},{910,213},{911,342},{912,41},{913,416},{914,170},{915,566},{916,84},{917,449},{918,341},{919,345},{920,45},{921,581},{922,171},{923,354},{924,221},{925,336},{926,174},{927,670},{928,9},{929,347},{930,308},{931,512},{932,86},{933,587},{934,176},{935,410},{936,82},{937,350},{938,233},{939,587},{940,90},{941,351},{942,293},{943,383},{944,23},{945,894},{946,221},{947,356},{948,152},{949,350},{950,194},{951,593},{952,56},{953,356},{954,337},{955,360},{956,90},{957,707},{958,180},{959,461},{960,8},{961,384},{962,174},{963,698},{964,89},{965,356},{966,422},{967,363},{968,55},{969,674},{970,176},{971,365},{972,184},{973,476},{974,183},{975,599},{976,21},{977,365},{978,311},{979,434},{980,120},{981,694},{982,185},{983,369},{984,77},{985,363},{986,179},{987,827},{988,101},{989,422},{990,416},{991,372},{992,12},{993,626},{994,246},{995,375},{996,161},{997,372},{998,188},{999,735},{1000,42},{1001,569},{1002,317},{1003,389},{1004,95},{1005,647},{1006,189},{1007,416},{1008,58},{1009,377},{1010,183},{1011,632},{1012,122},{1013,378},{1014,314},{1015,483},{1016,48},{1017,722},{1018,189},{1019,383},{1020,155},{1021,381},{1022,245},{1023,806},{1025,374},{1026,422},{1027,393},{1028,95},{1029,857},{1030,195},{1031,387},{1032,86},{1033,386},{1034,239},{1035,796},{1036,123},{1037,383},{1038,323},{1039,390},{1040,18},{1041,656},{1042,194},{1043,501},{1044,184},{1045,512},{1046,197},{1047,653},{1048,50},{1049,392},{1050,419},{1051,395},{1052,99},{1053,785},{1054,209},{1055,398},{1056,26},{1057,516},{1058,216},{1059,662},{1060,93},{1061,396},{1062,392},{1063,399},{1064,71},{1065,683},{1066,194},{1067,473},{1068,167},{1069,399},{1070,203},{1071,977},{1072,26},{1073,396},{1074,341},{1075,419},{1076,99},{1077,677},{1078,317},{1079,413},{1080,99},{1081,459},{1082,201},{1083,755},{1084,102},{1085,555},{1086,338},{1087,408},{1088,5},{1089,930},{1090,198},{1091,410},{1092,218},{1093,408},{1094,206},{1095,680},{1096,50},{1097,410},{1098,388},{1099,528},{1100,119},{1101,692},{1102,227},{1103,414},{1104,47},{1105,395},{1106,273},{1107,818},{1108,102},{1109,414},{1110,341},{1111,491},{1112,53},{1113,893},{1114,207},{1115,420},{1116,211},{1117,417},{1118,218},{1119,698},{1120,15},{1121,482},{1122,419},{1123,422},{1124,104},{1125,793},{1126,212},{1127,609},{1128,92},{1129,422},{1130,206},{1131,701},{1132,107},{1133,512},{1134,545},{1135,428},{1136,27},{1137,716},{1138,212},{1139,440},{1140,197},{1141,557},{1142,215},{1143,823},{1144,62},{1145,423},{1146,362},{1147,456},{1148,137},{1149,722},{1150,231},{1151,432},{1152,7},{1153,431},{1154,215},{1155,1097},{1156,106},{1157,428},{1158,362},{1159,479},{1160,48},{1161,899},{1162,287},{1163,437},{1164,182},{1165,431},{1166,257},{1167,728},{1168,26},{1169,570},{1170,409},{1171,440},{1172,108},{1173,797},{1174,221},{1175,456},{1176,122},{1177,533},{1178,260},{1179,851},{1180,113},{1181,441},{1182,368},{1183,567},{1184,12},{1185,758},{1186,221},{1187,446},{1188,263},{1189,440},{1190,281},{1191,743},{1192,54},{1193,446},{1194,377},{1195,450},{1196,120},{1197,1208},{1198,225},{1199,530},{1200,44},{1201,449},{1202,224},{1203,752},{1204,152},{1205,446},{1206,443},{1207,464},{1208,57},{1209,803},{1210,271},{1211,582},{1212,188},{1213,453},{1214,228},{1215,910},{1216,8},{1217,455},{1218,488},{1219,495},{1220,108},{1221,902},{1222,237},{1223,459},{1224,110},{1225,606},{1226,228},{1227,767},{1228,116},{1229,459},{1230,380},{1231,462},{1232,44},{1233,875},{1234,230},{1235,506},{1236,197},{1237,462},{1238,233},{1239,1031},{1240,60},{1241,461},{1242,498},{1243,551},{1244,117},{1245,797},{1246,299},{1247,488},{1248,23},{1249,467},{1250,228},{1251,902},{1252,116},{1253,611},{1254,518},{1255,473},{1256,57},{1257,791},{1258,230},{1259,473},{1260,286},{1261,467},{1262,237},{1263,788},{1264,30},{1265,608},{1266,401},{1267,609},{1268,117},{1269,975},{1270,240},{1271,506},{1272,98},{1273,545},{1274,315},{1275,788},{1276,140},{1277,477},{1278,466},{1279,480},{1281,1028},{1282,239},{1283,482},{1284,206},{1285,476},{1286,242},{1287,1079},{1288,84},{1289,482},{1290,422},{1291,485},{1292,134},{1293,812},{1294,243},{1295,618},{1296,62},{1297,485},{1298,299},{1299,812},{1300,111},{1301,486},{1302,557},{1303,489},{1304,62},{1305,919},{1306,243},{1307,491},{1308,203},{1309,746},{1310,248},{1311,986},{1312,14},{1313,486},{1314,467},{1315,495},{1316,165},{1317,827},{1318,248},{1319,495},{1320,122},{1321,494},{1322,246},{1323,1293},{1324,125},{1325,486},{1326,410},{1327,498},{1328,32},{1329,836},{1330,353},{1331,600},{1332,235},{1333,557},{1334,270},{1335,830},{1336,63},{1337,651},{1338,422},{1339,510},{1340,128},{1341,949},{1342,296},{1343,515},{1344,17},{1345,498},{1346,251},{1347,842},{1348,125},{1349,575},{1350,495},{1351,650},{1352,60},{1353,1004},{1354,252},{1355,510},{1356,212},{1357,572},{1358,326},{1359,976},{1360,26},{1361,509},{1362,431},{1363,531},{1364,161},{1365,1091},{1366,257},{1367,513},{1368,137},{1369,510},{1370,251},{1371,857},{1372,171},{1373,513},{1374,428},{1375,605},{1376,17},{1377,1031},{1378,252},{1379,663},{1380,233},{1381,516},{1382,260},{1383,863},{1384,63},{1385,513},{1386,749},{1387,575},{1388,131},{1389,872},{1390,263},{1391,530},{1392,53},{1393,678},{1394,257},{1395,1051},{1396,129},{1397,629},{1398,437},{1399,525},{1400,81},{1401,881},{1402,261},{1403,570},{1404,258},{1405,521},{1406,290},{1407,1166},{1408,5},{1409,527},{1410,458},{1411,542},{1412,131},{1413,1000},{1414,339},{1415,533},{1416,116},{1417,525},{1418,264},{1419,1103},{1420,135},{1421,705},{1422,517},{1423,534},{1424,32},{1425,983},{1426,309},{1427,536},{1428,287},{1429,534},{1430,311},{1431,1053},{1432,68},{1433,536},{1434,452},{1435,686},{1436,135},{1437,902},{1438,270},{1439,540},{1440,31},{1441,650},{1442,354},{1443,896},{1444,151},{1445,532},{1446,452},{1447,543},{1448,66},{1449,1435},{1450,261},{1451,545},{1452,275},{1453,543},{1454,273},{1455,905},{1456,42},{1457,606},{1458,549},{1459,548},{1460,131},{1461,917},{1462,287},{1463,923},{1464,113},{1465,543},{1466,273},{1467,1055},{1468,138},{1469,545},{1470,608},{1471,552},{1472,9},{1473,926},{1474,338},{1475,569},{1476,263},{1477,719},{1478,278},{1479,920},{1480,63},{1481,554},{1482,512},{1483,557},{1484,177},{1485,1295},{1486,279},{1487,558},{1488,62},{1489,557},{1490,273},{1491,1232},{1492,138},{1493,558},{1494,545},{1495,603},{1496,83},{1497,941},{1498,368},{1499,563},{1500,230},{1501,638},{1502,282},{1503,1078},{1504,18},{1505,758},{1506,476},{1507,668},{1508,135},{1509,947},{1510,285},{1511,567},{1512,180},{1513,563},{1514,282},{1515,941},{1516,143},{1517,563},{1518,611},{1519,804},{1520,38},{1521,1075},{1522,284},{1523,572},{1524,242},{1525,561},{1526,366},{1527,953},{1528,72},{1529,689},{1530,539},{1531,575},{1532,144},{1533,1232},{1534,296},{1535,578},{1536,2},{1537,570},{1538,287},{1539,1274},{1540,218},{1541,647},{1542,482},{1543,579},{1544,71},{1545,983},{1546,288},{1547,740},{1548,290},{1549,579},{1550,306},{1551,1196},{1552,35},{1553,581},{1554,623},{1555,585},{1556,144},{1557,1102},{1558,323},{1559,585},{1560,116},{1561,759},{1562,356},{1563,977},{1564,158},{1565,581},{1566,576},{1567,588},{1568,24},{1569,986},{1570,288},{1571,590},{1572,251},{1573,706},{1574,296},{1575,1432},{1576,72},{1577,671},{1578,497},{1579,593},{1580,150},{1581,1052},{1582,380},{1583,594},{1584,86},{1585,588},{1586,291},{1587,1082},{1588,147},{1589,773},{1590,491},{1591,623},{1592,75},{1593,1217},{1594,297},{1595,701},{1596,356},{1597,597},{1598,311},{1599,995},{1600,6},{1601,599},{1602,569},{1603,771},{1604,149},{1605,1022},{1606,356},{1607,603},{1608,131},{1609,602},{1610,420},{1611,1157},{1612,159},{1613,603},{1614,503},{1615,665},{1616,36},{1617,1586},{1618,302},{1619,608},{1620,302},{1621,606},{1622,305},{1623,1013},{1624,96},{1625,594},{1626,512},{1627,611},{1628,179},{1629,1153},{1630,308},{1631,785},{1632,32},{1633,684},{1634,356},{1635,1016},{1636,152},{1637,612},{1638,745},{1639,725},{1640,71},{1641,1031},{1642,306},{1643,654},{1644,257},{1645,825},{1646,309},{1647,1212},{1648,39},{1649,614},{1650,608},{1651,627},{1652,206},{1653,1142},{1654,311},{1655,623},{1656,160},{1657,620},{1658,309},{1659,1367},{1660,158},{1661,746},{1662,518},{1663,624},{1664,3},{1665,1174},{1666,413},{1667,626},{1668,266},{1669,624},{1670,315},{1671,1043},{1672,104},{1673,813},{1674,657},{1675,644},{1676,158},{1677,1097},{1678,315},{1679,683},{1680,83},{1681,628},{1682,312},{1683,1418},{1684,156},{1685,626},{1686,527},{1687,812},{1688,80},{1689,1061},{1690,306},{1691,701},{1692,313},{1693,633},{1694,490},{1695,1055},{1696,18},{1697,635},{1698,536},{1699,638},{1700,149},{1701,1639},{1702,345},{1703,647},{1704,137},{1705,803},{1706,318},{1707,1067},{1708,204},{1709,639},{1710,671},{1711,662},{1712,41},{1713,1076},{1714,320},{1715,855},{1716,317},{1717,638},{1718,323},{1719,1231},{1720,83},{1721,644},{1722,692},{1723,647},{1724,162},{1725,1169},{1726,324},{1727,764},{1728,21},{1729,920},{1730,318},{1731,1082},{1732,161},{1733,648},{1734,542},{1735,653},{1736,111},{1737,1232},{1738,395},{1739,678},{1740,266},{1741,651},{1742,335},{1743,1436},{1744,39},{1745,648},{1746,620},{1747,656},{1748,197},{1749,1292},{1750,417},{1751,668},{1752,137},{1753,656},{1754,327},{1755,1287},{1756,165},{1757,854},{1758,548},{1759,660},{1760,23},{1761,1106},{1762,329},{1763,692},{1764,415},{1765,656},{1766,332},{1767,1301},{1768,77},{1769,657},{1770,572},{1771,1097},{1772,167},{1773,1255},{1774,333},{1775,681},{1776,68},{1777,665},{1778,435},{1779,1112},{1780,161},{1781,662},{1782,791},{1783,669},{1784,84},{1785,1430},{1786,386},{1787,671},{1788,278},{1789,669},{1790,338},{1791,1282},{1792,3},{1793,806},{1794,608},{1795,675},{1796,167},{1797,1127},{1798,357},{1799,866},{1800,157},{1801,674},{1802,332},{1803,1127},{1804,200},{1805,751},{1806,761},{1807,686},{1808,41},{1809,1376},{1810,333},{1811,680},{1812,287},{1813,900},{1814,341},{1815,1361},{1816,86},{1817,759},{1818,643},{1819,695},{1820,213},{1821,1142},{1822,342},{1823,684},{1824,41},{1825,674},{1826,416},{1827,1663},{1828,170},{1829,755},{1830,566},{1831,687},{1832,84},{1833,1193},{1834,449},{1835,690},{1836,341},{1837,824},{1838,345},{1839,1148},{1840,45},{1841,894},{1842,581},{1843,764},{1844,171},{1845,1304},{1846,354},{1847,693},{1848,221},{1849,727},{1850,336},{1851,1157},{1852,174},{1853,689},{1854,670},{1855,888},{1856,9},{1857,1166},{1858,347},{1859,821},{1860,308},{1861,696},{1862,512},{1863,1511},{1864,86},{1865,693},{1866,587},{1867,701},{1868,176},{1869,1502},{1870,410},{1871,702},{1872,82},{1873,701},{1874,350},{1875,1166},{1876,233},{1877,702},{1878,587},{1879,705},{1880,90},{1881,1751},{1882,351},{1883,906},{1884,293},{1885,687},{1886,383},{1887,1175},{1888,23},{1889,707},{1890,894},{1891,753},{1892,221},{1893,1187},{1894,356},{1895,713},{1896,152},{1897,921},{1898,350},{1899,1361},{1900,194},{1901,711},{1902,593},{1903,842},{1904,56},{1905,1208},{1906,356},{1907,716},{1908,337},{1909,797},{1910,360},{1911,1583},{1912,90},{1913,716},{1914,707},{1915,720},{1916,180},{1917,1452},{1918,461},{1919,794},{1920,8},{1921,716},{1922,384},{1923,1202},{1924,174},{1925,1094},{1926,698},{1927,752},{1928,89},{1929,1211},{1930,356},{1931,725},{1932,422},{1933,723},{1934,363},{1935,1436},{1936,55},{1937,720},{1938,674},{1939,933},{1940,176},{1941,1217},{1942,365},{1943,749},{1944,184},{1945,723},{1946,476},{1947,1493},{1948,183},{1949,729},{1950,599},{1951,732},{1952,21},{1953,1894},{1954,365},{1955,791},{1956,311},{1957,827},{1958,434},{1959,1223},{1960,120},{1961,729},{1962,694},{1963,744},{1964,185},{1965,1247},{1966,369},{1967,947},{1968,77},{1969,884},{1970,363},{1971,1454},{1972,179},{1973,738},{1974,827},{1975,756},{1976,101},{1977,1241},{1978,422},{1979,743},{1980,416},{1981,962},{1982,372},{1983,1238},{1984,12},{1985,738},{1986,626},{1987,746},{1988,246},{1989,1406},{1990,375},{1991,881},{1992,161},{1993,746},{1994,372},{1995,1772},{1996,188},{1997,747},{1998,735},{1999,750},{2000,42},{2001,1358},{2002,569},{2003,752},{2004,317},{2005,746},{2006,389},{2007,1435},{2008,95},{2009,998},{2010,647},{2011,755},{2012,189},{2013,1487},{2014,416},{2015,798},{2016,58},{2017,755},{2018,377},{2019,1262},{2020,183},{2021,827},{2022,632},{2023,973},{2024,122},{2025,1508},{2026,378},{2027,761},{2028,314},{2029,759},{2030,483},{2031,1268},{2032,48},{2033,860},{2034,722},{2035,896},{2036,189},{2037,1637},{2038,383},{2039,765},{2040,155},{2041,759},{2042,381},{2043,1463},{2044,245},{2045,761},{2046,806},{2047,833},{2049,1286},{2050,374},{2051,987},{2052,422},{2053,768},{2054,393},{2055,1280},{2056,95},{2057,926},{2058,857},{2059,792},{2060,195},{2061,1459},{2062,387},{2063,774},{2064,86},{2065,1028},{2066,386},{2067,1286},{2068,239},{2069,774},{2070,796},{2071,857},{2072,123},{2073,1301},{2074,383},{2075,794},{2076,323},{2077,854},{2078,390},{2079,2330},{2080,18},{2081,779},{2082,656},{2083,782},{2084,194},{2085,1322},{2086,501},{2087,783},{2088,184},{2089,782},{2090,512},{2091,1307},{2092,197},{2093,1095},{2094,653},{2095,788},{2096,50},{2097,1487},{2098,392},{2099,788},{2100,419},{2101,941},{2102,395},{2103,1313},{2104,99},{2105,783},{2106,785},{2107,1097},{2108,209},{2109,1457},{2110,398},{2111,792},{2112,26},{2113,791},{2114,516},{2115,1561},{2116,216},{2117,788},{2118,662},{2119,803},{2120,93},{2121,1703},{2122,396},{2123,941},{2124,392},{2125,782},{2126,399},{2127,1328},{2128,71},{2129,797},{2130,683},{2131,800},{2132,194},{2133,1611},{2134,473},{2135,1023},{2136,167},{2137,800},{2138,399},{2139,1547},{2140,203},{2141,801},{2142,977},{2143,804},{2144,26},{2145,1580},{2146,396},{2147,890},{2148,341},{2149,1043},{2150,419},{2151,1537},{2152,99},{2153,806},{2154,677},{2155,810},{2156,317},{2157,1352},{2158,413},{2159,821},{2160,99},{2161,809},{2162,459},{2163,1772},{2164,201},{2165,806},{2166,755},{2167,959},{2168,102},{2169,1538},{2170,555},{2171,822},{2172,338},{2173,809},{2174,408},{2175,1349},{2176,5},{2177,1056},{2178,930},{2179,818},{2180,198},{2181,1367},{2182,410},{2183,845},{2184,218},{2185,983},{2186,408},{2187,1643},{2188,206},{2189,980},{2190,680},{2191,1055},{2192,50},{2193,1439},{2194,410},{2195,825},{2196,388},{2197,819},{2198,528},{2199,1373},{2200,119},{2201,903},{2202,692},{2203,827},{2204,227},{2205,2071},{2206,414},{2207,828},{2208,47},{2209,864},{2210,395},{2211,1688},{2212,273},{2213,828},{2214,818},{2215,833},{2216,102},{2217,1391},{2218,414},{2219,1068},{2220,341},{2221,831},{2222,491},{2223,1742},{2224,53},{2225,824},{2226,893},{2227,848},{2228,207},{2229,1397},{2230,420},{2231,908},{2232,211},{2233,1271},{2234,417},{2235,1391},{2236,218},{2237,837},{2238,698},{2239,840},{2240,15},{2241,1694},{2242,482},{2243,842},{2244,419},{2245,836},{2246,422},{2247,1841},{2248,104},{2249,837},{2250,793},{2251,845},{2252,212},{2253,1412},{2254,609},{2255,995},{2256,92},{2257,840},{2258,422},{2259,1616},{2260,206},{2261,1205},{2262,701},{2263,902},{2264,107},{2265,1433},{2266,512},{2267,851},{2268,545},{2269,849},{2270,428},{2271,1418},{2272,27},{2273,851},{2274,716},{2275,1086},{2276,212},{2277,2075},{2278,440},{2279,893},{2280,197},{2281,854},{2282,557},{2283,1427},{2284,215},{2285,851},{2286,823},{2287,858},{2288,62},{2289,1838},{2290,423},{2291,879},{2292,362},{2293,858},{2294,456},{2295,1688},{2296,137},{2297,860},{2298,722},{2299,1145},{2300,231},{2301,1487},{2302,432},{2303,1194},{2304,7},{2305,858},{2306,431},{2307,1442},{2308,215},{2309,864},{2310,1097},{2311,867},{2312,106},{2313,1640},{2314,428},{2315,870},{2316,362},{2317,1124},{2318,479},{2319,1448},{2320,48},{2321,1040},{2322,899},{2323,945},{2324,287},{2325,1544},{2326,437},{2327,881},{2328,182},{2329,869},{2330,431},{2331,2122},{2332,257},{2333,873},{2334,728},{2335,878},{2336,26},{2337,1619},{2338,570},{2339,878},{2340,409},{2341,876},{2342,440},{2343,1781},{2344,108},{2345,1163},{2346,797},{2347,881},{2348,221},{2349,1751},{2350,456},{2351,882},{2352,122},{2353,876},{2354,533},{2355,1466},{2356,260},{2357,882},{2358,851},{2359,1136},{2360,113},{2361,1481},{2362,441},{2363,899},{2364,368},{2365,1097},{2366,567},{2367,1690},{2368,12},{2369,984},{2370,758},{2371,890},{2372,221},{2373,1907},{2374,446},{2375,980},{2376,263},{2377,890},{2378,440},{2379,1481},{2380,281},{2381,891},{2382,743},{2383,894},{2384,54},{2385,1684},{2386,446},{2387,1448},{2388,377},{2389,894},{2390,450},{2391,1493},{2392,120},{2393,896},{2394,1208},{2395,900},{2396,225},{2397,1562},{2398,530},{2399,900},{2400,44},{2401,1200},{2402,449},{2403,1772},{2404,224},{2405,882},{2406,752},{2407,923},{2408,152},{2409,1784},{2410,446},{2411,905},{2412,443},{2413,1016},{2414,464},{2415,2108},{2416,57},{2417,905},{2418,803},{2419,938},{2420,271},{2421,1714},{2422,582},{2423,909},{2424,188},{2425,899},{2426,453},{2427,1517},{2428,228},{2429,1178},{2430,910},{2431,1073},{2432,8},{2433,1526},{2434,455},{2435,915},{2436,488},{2437,912},{2438,495},{2439,1741},{2440,108},{2441,914},{2442,902},{2443,1176},{2444,237},{2445,1547},{2446,459},{2447,918},{2448,110},{2449,1002},{2450,606},{2451,1778},{2452,228},{2453,1097},{2454,767},{2455,923},{2456,116},{2457,2325},{2458,459},{2459,923},{2460,380},{2461,1022},{2462,462},{2463,1538},{2464,44},{2465,905},{2466,875},{2467,926},{2468,230},{2469,1547},{2470,506},{2471,1190},{2472,197},{2473,926},{2474,462},{2475,2072},{2476,233},{2477,927},{2478,1031},{2479,956},{2480,60},{2481,1556},{2482,461},{2483,939},{2484,498},{2485,1230},{2486,551},{2487,1553},{2488,117},{2489,1049},{2490,797},{2491,972},{2492,299},{2493,1765},{2494,488},{2495,938},{2496,23},{2497,1118},{2498,467},{2499,2072},{2500,228},{2501,932},{2502,902},{2503,939},{2504,116},{2505,1583},{2506,611},{2507,1020},{2508,518},{2509,935},{2510,473},{2511,1994},{2512,57},{2513,1218},{2514,791},{2515,945},{2516,230},{2517,1577},{2518,473},{2519,1115},{2520,286},{2521,944},{2522,467},{2523,1574},{2524,237},{2525,936},{2526,788},{2527,1354},{2528,30},{2529,1793},{2530,608},{2531,950},{2532,401},{2533,944},{2534,609},{2535,1574},{2536,117},{2537,1031},{2538,975},{2539,953},{2540,240},{2541,2450},{2542,506},{2543,954},{2544,98},{2545,948},{2546,545},{2547,1820},{2548,315},{2549,954},{2550,788},{2551,957},{2552,140},{2553,1733},{2554,477},{2555,1226},{2556,466},{2557,957},{2558,480},{2559,1598},{2561,954},{2562,1028},{2563,1136},{2564,239},{2565,2090},{2566,482},{2567,974},{2568,206},{2569,1245},{2570,476},{2571,1607},{2572,242},{2573,1052},{2574,1079},{2575,981},{2576,84},{2577,1616},{2578,482},{2579,968},{2580,422},{2581,962},{2582,485},{2583,2354},{2584,134},{2585,1193},{2586,812},{2587,978},{2588,243},{2589,1622},{2590,618},{2591,972},{2592,62},{2593,971},{2594,485},{2595,1616},{2596,299},{2597,1290},{2598,812},{2599,1058},{2600,111},{2601,1845},{2602,486},{2603,1079},{2604,557},{2605,971},{2606,489},{2607,1976},{2608,62},{2609,977},{2610,919},{2611,1257},{2612,243},{2613,1682},{2614,491},{2615,983},{2616,203},{2617,980},{2618,746},{2619,1931},{2620,248},{2621,981},{2622,986},{2623,1028},{2624,14},{2625,2105},{2626,486},{2627,1011},{2628,467},{2629,1175},{2630,495},{2631,1643},{2632,165},{2633,986},{2634,827},{2635,1046},{2636,248},{2637,1867},{2638,495},{2639,1266},{2640,122},{2641,1112},{2642,494},{2643,1652},{2644,246},{2645,1080},{2646,1293},{2647,993},{2648,125},{2649,1661},{2650,486},{2651,1175},{2652,410},{2653,1286},{2654,498},{2655,1946},{2656,32},{2657,995},{2658,836},{2659,998},{2660,353},{2661,1667},{2662,600},{2663,999},{2664,235},{2665,980},{2666,557},{2667,2177},{2668,270},{2669,995},{2670,830},{2671,1002},{2672,63},{2673,2372},{2674,651},{2675,1019},{2676,422},{2677,1002},{2678,510},{2679,1931},{2680,128},{2681,1299},{2682,949},{2683,1007},{2684,296},{2685,1697},{2686,515},{2687,1008},{2688,17},{2689,1007},{2690,498},{2691,2071},{2692,251},{2693,1008},{2694,842},{2695,1583},{2696,125},{2697,1793},{2698,575},{2699,1013},{2700,495},{2701,1007},{2702,650},{2703,1685},{2704,60},{2705,1008},{2706,1004},{2707,1016},{2708,252},{2709,2585},{2710,510},{2711,1017},{2712,212},{2713,1016},{2714,572},{2715,1691},{2716,326},{2717,1331},{2718,976},{2719,1020},{2720,26},{2721,1706},{2722,509},{2723,1311},{2724,431},{2725,1011},{2726,531},{2727,2007},{2728,161},{2729,1022},{2730,1091},{2731,1025},{2732,257},{2733,1712},{2734,513},{2735,1028},{2736,137},{2737,1433},{2738,510},{2739,2078},{2740,251},{2741,1026},{2742,857},{2743,1037},{2744,171},{2745,1939},{2746,513},{2747,1061},{2748,428},{2749,1029},{2750,605},{2751,2246},{2752,17},{2753,1031},{2754,1031},{2755,1136},{2756,252},{2757,1727},{2758,663},{2759,1100},{2760,233},{2761,1235},{2762,516},{2763,1973},{2764,260},{2765,1365},{2766,863},{2767,1038},{2768,63},{2769,1778},{2770,513},{2771,1052},{2772,749},{2773,1121},{2774,575},{2775,1724},{2776,131},{2777,1040},{2778,872},{2779,1338},{2780,263},{2781,2088},{2782,530},{2783,1360},{2784,53},{2785,1038},{2786,678},{2787,1742},{2788,257},{2789,1044},{2790,1051},{2791,1047},{2792,129},{2793,2561},{2794,629},{2795,1091},{2796,437},{2797,1047},{2798,525},{2799,1996},{2800,81},{2801,1049},{2802,881},{2803,1052},{2804,261},{2805,2072},{2806,570},{2807,1352},{2808,258},{2809,1050},{2810,521},{2811,1757},{2812,290},{2813,1049},{2814,1166},{2815,1058},{2816,5},{2817,1997},{2818,527},{2819,1058},{2820,458},{2821,1446},{2822,542},{2823,1763},{2824,131},{2825,1049},{2826,1000},{2827,1253},{2828,339},{2829,1922},{2830,533},{2831,1172},{2832,116},{2833,1061},{2834,525},{2835,2717},{2836,264},{2837,1062},{2838,1103},{2839,1076},{2840,135},{2841,1781},{2842,705},{2843,1067},{2844,517},{2845,1061},{2846,534},{2847,1775},{2848,32},{2849,1622},{2850,983},{2851,1070},{2852,309},{2853,2020},{2854,536},{2855,1073},{2856,287},{2857,1070},{2858,534},{2859,1787},{2860,311},{2861,1071},{2862,1053},{2863,1379},{2864,68},{2865,1808},{2866,536},{2867,1119},{2868,452},{2869,1205},{2870,686},{2871,2405},{2872,135},{2873,1067},{2874,902},{2875,1167},{2876,270},{2877,2312},{2878,540},{2879,1080},{2880,31},{2881,1166},{2882,650},{2883,1922},{2884,354},{2885,1076},{2886,896},{2887,1083},{2888,151},{2889,2171},{2890,532},{2891,1487},{2892,452},{2893,1292},{2894,543},{2895,1805},{2896,66},{2897,1085},{2898,1435},{2899,1095},{2900,261},{2901,1817},{2902,545},{2903,1089},{2904,275},{2905,1433},{2906,543},{2907,2285},{2908,273},{2909,1089},{2910,905},{2911,1121},{2912,42},{2913,1826},{2914,606},{2915,1286},{2916,549},{2917,1092},{2918,548},{2919,2381},{2920,131},{2921,1209},{2922,917},{2923,1122},{2924,287},{2925,2062},{2926,923},{2927,1098},{2928,113},{2929,1092},{2930,543},{2931,1832},{2932,273},{2933,1421},{2934,1055},{2935,1103},{2936,138},{2937,2174},{2938,545},{2939,1103},{2940,608},{2941,1097},{2942,552},{2943,2166},{2944,9},{2945,1298},{2946,926},{2947,1419},{2948,338},{2949,1847},{2950,569},{2951,1115},{2952,263},{2953,1106},{2954,719},{2955,1841},{2956,278},{2957,1107},{2958,920},{2959,1310},{2960,63},{2961,2812},{2962,554},{2963,1112},{2964,512},{2965,1106},{2966,557},{2967,2111},{2968,177},{2969,1112},{2970,1295},{2971,1115},{2972,279},{2973,1862},{2974,558},{2975,1424},{2976,62},{2977,1110},{2978,557},{2979,2126},{2980,273},{2981,1331},{2982,1232},{2983,1235},{2984,138},{2985,1883},{2986,558},{2987,1140},{2988,545},{2989,1485},{2990,603},{2991,1868},{2992,83},{2993,1118},{2994,941},{2995,1125},{2996,368},{2997,2234},{2998,563},{2999,1125},{3000,230},{3001,1124},{3002,638},{3003,2852},{3004,282},{3005,1121},{3006,1078},{3007,1199},{3008,18},{3009,1949},{3010,758},{3011,1130},{3012,476},{3013,1247},{3014,668},{3015,2201},{3016,135},{3017,1461},{3018,947},{3019,1133},{3020,285},{3021,2087},{3022,567},{3023,1134},{3024,180},{3025,1357},{3026,563},{3027,1892},{3028,282},{3029,1130},{3030,941},{3031,1460},{3032,143},{3033,2150},{3034,563},{3035,1140},{3036,611},{3037,1137},{3038,804},{3039,1898},{3040,38},{3041,1139},{3042,1075},{3043,1154},{3044,284},{3045,2441},{3046,572},{3047,1349},{3048,242},{3049,1142},{3050,561},{3051,2249},{3052,366},{3053,1232},{3054,953},{3055,1188},{3056,72},{3057,1916},{3058,689},{3059,1772},{3060,539},{3061,1146},{3062,575},{3063,1913},{3064,144},{3065,1143},{3066,1232},{3067,1151},{3068,296},{3069,2738},{3070,578},{3071,1178},{3072,2},{3073,1488},{3074,570},{3075,1913},{3076,287},{3077,1148},{3078,1274},{3079,1155},{3080,218},{3081,1973},{3082,647},{3083,1157},{3084,482},{3085,1151},{3086,579},{3087,2914},{3088,71},{3089,1157},{3090,983},{3091,1370},{3092,288},{3093,1937},{3094,740},{3095,1163},{3096,290},{3097,1301},{3098,579},{3099,1937},{3100,306},{3101,1502},{3102,1196},{3103,1184},{3104,35},{3105,2484},{3106,581},{3107,1173},{3108,623},{3109,1164},{3110,585},{3111,1940},{3112,144},{3113,1391},{3114,1102},{3115,1496},{3116,323},{3117,1952},{3118,585},{3119,1170},{3120,116},{3121,1169},{3122,759},{3123,2228},{3124,356},{3125,1164},{3126,977},{3127,1211},{3128,158},{3129,2513},{3130,581},{3131,1248},{3132,576},{3133,1169},{3134,588},{3135,2564},{3136,24},{3137,1175},{3138,986},{3139,1232},{3140,288},{3141,2224},{3142,590},{3143,1514},{3144,251},{3145,1160},{3146,706},{3147,1967},{3148,296},{3149,1268},{3150,1432},{3151,1283},{3152,72},{3153,1976},{3154,671},{3155,1185},{3156,497},{3157,1799},{3158,593},{3159,2365},{3160,150},{3161,1179},{3162,1052},{3163,1187},{3164,380},{3165,1997},{3166,594},{3167,1188},{3168,86},{3169,1187},{3170,588},{3171,2582},{3172,291},{3173,1331},{3174,1082},{3175,1206},{3176,147},{3177,2252},{3178,773},{3179,1409},{3180,491},{3181,1191},{3182,623},{3183,1988},{3184,75},{3185,1578},{3186,1217},{3187,1196},{3188,297},{3189,1997},{3190,701},{3191,1197},{3192,356},{3193,1299},{3194,597},{3195,2326},{3196,311},{3197,1322},{3198,995},{3199,1541},{3200,6},{3201,2369},{3202,599},{3203,1202},{3204,569},{3205,1196},{3206,771},{3207,2003},{3208,149},{3209,1202},{3210,1022},{3211,1328},{3212,356},{3213,3044},{3214,603},{3215,1208},{3216,131},{3217,1205},{3218,602},{3219,2006},{3220,420},{3221,1206},{3222,1157},{3223,1427},{3224,159},{3225,2108},{3226,603},{3227,1554},{3228,503},{3229,1209},{3230,665},{3231,2302},{3232,36},{3233,1206},{3234,1586},{3235,1215},{3236,302},{3237,2072},{3238,608},{3239,1244},{3240,302},{3241,1569},{3242,606},{3243,2297},{3244,305},{3245,1487},{3246,1013},{3247,1229},{3248,96},{3249,2562},{3250,594},{3251,1220},{3252,512},{3253,1218},{3254,611},{3255,2783},{3256,179},{3257,1220},{3258,1153},{3259,1223},{3260,308},{3261,2042},{3262,785},{3263,1232},{3264,32},{3265,1218},{3266,684},{3267,2890},{3268,356},{3269,1583},{3270,1016},{3271,1227},{3272,152},{3273,2051},{3274,612},{3275,1244},{3276,745},{3277,1223},{3278,725},{3279,2048},{3280,71},{3281,1226},{3282,1031},{3283,1682},{3284,306},{3285,2324},{3286,654},{3287,1361},{3288,257},{3289,1583},{3290,825},{3291,2057},{3292,309},{3293,1229},{3294,1212},{3295,1238},{3296,39},{3297,2648},{3298,614},{3299,1238},{3300,608},{3301,1236},{3302,627},{3303,2353},{3304,206},{3305,1233},{3306,1142},{3307,1241},{3308,311},{3309,2072},{3310,623},{3311,1976},{3312,160},{3313,1241},{3314,620},{3315,2054},{3316,309},{3317,1349},{3318,1367},{3319,1245},{3320,158},{3321,2480},{3322,746},{3323,1247},{3324,518},{3325,1769},{3326,624},{3327,2078},{3328,3},{3329,1247},{3330,1174},{3331,1250},{3332,413},{3333,2462},{3334,626},{3335,1353},{3336,266},{3337,1341},{3338,624},{3339,3040},{3340,315},{3341,1247},{3342,1043},{3343,1254},{3344,104},{3345,2108},{3346,813},{3347,1256},{3348,657},{3349,1250},{3350,644},{3351,2093},{3352,158},{3353,1623},{3354,1097},{3355,1481},{3356,315},{3357,2377},{3358,683},{3359,1260},{3360,83},{3361,1259},{3362,628},{3363,2408},{3364,312},{3365,1256},{3366,1418},{3367,1617},{3368,156},{3369,2111},{3370,626},{3371,1265},{3372,527},{3373,1263},{3374,812},{3375,2481},{3376,80},{3377,1508},{3378,1061},{3379,1347},{3380,306},{3381,3047},{3382,701},{3383,1280},{3384,313},{3385,1263},{3386,633},{3387,2117},{3388,490},{3389,1269},{3390,1055},{3391,1272},{3392,18},{3393,2398},{3394,635},{3395,1631},{3396,536},{3397,1367},{3398,638},{3399,2561},{3400,149},{3401,1427},{3402,1639},{3403,1307},{3404,345},{3405,2147},{3406,647},{3407,1278},{3408,137},{3409,1650},{3410,803},{3411,2432},{3412,318},{3413,1278},{3414,1067},{3415,1283},{3416,204},{3417,2204},{3418,639},{3419,1290},{3420,671},{3421,1526},{3422,662},{3423,2786},{3424,41},{3425,1274},{3426,1076},{3427,1395},{3428,320},{3429,2565},{3430,855},{3431,1340},{3432,317},{3433,1286},{3434,638},{3435,2141},{3436,323},{3437,1664},{3438,1231},{3439,1424},{3440,83},{3441,2288},{3442,644},{3443,1526},{3444,692},{3445,1272},{3446,647},{3447,2455},{3448,162},{3449,1292},{3450,1169},{3451,1658},{3452,324},{3453,2162},{3454,764},{3455,1298},{3456,21},{3457,1295},{3458,920},{3459,2162},{3460,318},{3461,1296},{3462,1082},{3463,1299},{3464,161},{3465,3731},{3466,648},{3467,1301},{3468,542},{3469,1299},{3470,653},{3471,2165},{3472,111},{3473,1434},{3474,1232},{3475,1319},{3476,395},{3477,2402},{3478,678},{3479,1779},{3480,266},{3481,1351},{3482,651},{3483,2723},{3484,335},{3485,1289},{3486,1436},{3487,1544},{3488,39},{3489,2186},{3490,648},{3491,1310},{3492,620},{3493,1691},{3494,656},{3495,2180},{3496,197},{3497,1305},{3498,1292},{3499,1313},{3500,417},{3501,2479},{3502,668},{3503,1397},{3504,137},{3505,1308},{3506,656},{3507,2852},{3508,327},{3509,1576},{3510,1287},{3511,1317},{3512,165},{3513,2201},{3514,854},{3515,1451},{3516,548},{3517,1317},{3518,660},{3519,2711},{3520,23},{3521,1704},{3522,1106},{3523,1329},{3524,329},{3525,2294},{3526,692},{3527,1323},{3528,415},{3529,1322},{3530,656},{3531,2663},{3532,332},{3533,1323},{3534,1301},{3535,1698},{3536,77},{3537,2648},{3538,657},{3539,1328},{3540,572},{3541,1326},{3542,1097},{3543,2213},{3544,167},{3545,1323},{3546,1255},{3547,1331},{3548,333},{3549,2849},{3550,681},{3551,1370},{3552,68},{3553,1745},{3554,665},{3555,2581},{3556,435},{3557,1332},{3558,1112},{3559,1335},{3560,161},{3561,2231},{3562,662},{3563,1716},{3564,791},{3565,1545},{3566,669},{3567,2225},{3568,84},{3569,1436},{3570,1430},{3571,1340},{3572,386},{3573,2530},{3574,671},{3575,1574},{3576,278},{3577,1778},{3578,669},{3579,2237},{3580,338},{3581,1341},{3582,1282},{3583,1344},{3584,3},{3585,2258},{3586,806},{3587,1358},{3588,608},{3589,1340},{3590,675},{3591,3761},{3592,167},{3593,1346},{3594,1127},{3595,1350},{3596,357},{3597,2657},{3598,866},{3599,1394},{3600,157},{3601,1344},{3602,674},{3603,2252},{3604,332},{3605,1770},{3606,1127},{3607,1353},{3608,200},{3609,2558},{3610,751},{3611,1470},{3612,761},{3613,1353},{3614,686},{3615,2255},{3616,41},{3617,1355},{3618,1376},{3619,2150},{3620,333},{3621,2327},{3622,680},{3623,1359},{3624,287},{3625,1344},{3626,900},{3627,2734},{3628,341},{3629,1520},{3630,1361},{3631,1362},{3632,86},{3633,2918},{3634,759},{3635,1365},{3636,643},{3637,1362},{3638,695},{3639,2273},{3640,213},{3641,1625},{3642,1142},{3643,1367},{3644,342},{3645,2733},{3646,684},{3647,1757},{3648,41},{3649,1364},{3650,674},{3651,2282},{3652,416},{3653,1364},{3654,1663},{3655,1430},{3656,170},{3657,2483},{3658,755},{3659,1373},{3660,566},{3661,1772},{3662,687},{3663,3068},{3664,84},{3665,1368},{3666,1193},{3667,1520},{3668,449},{3669,2297},{3670,690},{3671,1377},{3672,341},{3673,1376},{3674,824},{3675,3044},{3676,345},{3677,1377},{3678,1148},{3679,1388},{3680,45},{3681,2609},{3682,894},{3683,1401},{3684,581},{3685,1682},{3686,764},{3687,2303},{3688,171},{3689,1892},{3690,1304},{3691,1385},{3692,354},{3693,2312},{3694,693},{3695,1388},{3696,221},{3697,1385},{3698,727},{3699,2726},{3700,336},{3701,1386},{3702,1157},{3703,1947},{3704,174},{3705,2555},{3706,689},{3707,1643},{3708,670},{3709,1389},{3710,888},{3711,2318},{3712,9},{3713,1488},{3714,1166},{3715,1395},{3716,347},{3717,3503},{3718,821},{3719,1395},{3720,308},{3721,1392},{3722,696},{3723,2327},{3724,512},{3725,1386},{3726,1511},{3727,1398},{3728,86},{3729,2759},{3730,693},{3731,1793},{3732,587},{3733,1398},{3734,701},{3735,2711},{3736,176},{3737,1395},{3738,1502},{3739,1403},{3740,410},{3741,2447},{3742,702},{3743,1550},{3744,82},{3745,1838},{3746,701},{3747,2342},{3748,350},{3749,1547},{3750,1166},{3751,1795},{3752,233},{3753,2807},{3754,702},{3755,1410},{3756,587},{3757,1399},{3758,705},{3759,3056},{3760,90},{3761,1409},{3762,1751},{3763,1449},{3764,351},{3765,2372},{3766,906},{3767,1413},{3768,293},{3769,1412},{3770,687},{3771,2687},{3772,383},{3773,2228},{3774,1175},{3775,1431},{3776,23},{3777,2366},{3778,707},{3779,1418},{3780,894},{3781,1583},{3782,753},{3783,2360},{3784,221},{3785,1413},{3786,1187},{3787,1824},{3788,356},{3789,2683},{3790,713},{3791,1433},{3792,152},{3793,1421},{3794,921},{3795,3047},{3796,350},{3797,1422},{3798,1361},{3799,1445},{3800,194},{3801,3053},{3802,711},{3803,1427},{3804,593},{3805,1421},{3806,842},{3807,2960},{3808,56},{3809,1422},{3810,1208},{3811,1455},{3812,356},{3813,2537},{3814,716},{3815,1833},{3816,337},{3817,1703},{3818,797},{3819,2723},{3820,360},{3821,1431},{3822,1583},{3823,1434},{3824,90},{3825,2702},{3826,716},{3827,1502},{3828,707},{3829,1853},{3830,720},{3831,2393},{3832,180},{3833,1436},{3834,1452},{3835,1481},{3836,461},{3837,2402},{3838,794},{3839,1700},{3840,8},{3841,1584},{3842,716},{3843,3499},{3844,384},{3845,1436},{3846,1202},{3847,1443},{3848,174},{3849,2411},{3850,1094},{3851,1445},{3852,698},{3853,1443},{3854,752},{3855,2405},{3856,89},{3857,2054},{3858,1211},{3859,1460},{3860,356},{3861,3362},{3862,725},{3863,1449},{3864,422},{3865,1443},{3866,723},{3867,2417},{3868,363},{3869,1445},{3870,1436},{3871,1974},{3872,55},{3873,2426},{3874,720},{3875,1542},{3876,674},{3877,1452},{3878,933},{3879,2761},{3880,176},{3881,1454},{3882,1217},{3883,1721},{3884,365},{3885,3116},{3886,749},{3887,1581},{3888,184},{3889,1457},{3890,723},{3891,2432},{3892,476},{3893,1454},{3894,1493},{3895,1610},{3896,183},{3897,2762},{3898,729},{3899,1878},{3900,599},{3901,1562},{3902,732},{3903,2438},{3904,21},{3905,1778},{3906,1894},{3907,1466},{3908,365},{3909,2447},{3910,791},{3911,1467},{3912,311},{3913,1973},{3914,827},{3915,2877},{3916,434},{3917,1467},{3918,1223},{3919,1470},{3920,120},{3921,2456},{3922,729},{3923,1472},{3924,694},{3925,1461},{3926,744},{3927,3734},{3928,185},{3929,1472},{3930,1247},{3931,1475},{3932,369},{3933,3350},{3934,947},{3935,1478},{3936,77},{3937,1596},{3938,884},{3939,2456},{3940,363},{3941,1907},{3942,1454},{3943,1479},{3944,179},{3945,2483},{3946,738},{3947,1481},{3948,827},{3949,1760},{3950,756},{3951,2812},{3952,101},{3953,1580},{3954,1241},{3955,1901},{3956,422},{3957,2477},{3958,743},{3959,1511},{3960,416},{3961,1481},{3962,962},{3963,2477},{3964,372},{3965,1467},{3966,1238},{3967,1488},{3968,12},{3969,3926},{3970,738},{3971,1958},{3972,626},{3973,1484},{3974,746},{3975,2474},{3976,246},{3977,1487},{3978,1406},{3979,1620},{3980,375},{3981,2492},{3982,881},{3983,1919},{3984,161},{3985,1488},{3986,746},{3987,2840},{3988,372},{3989,1494},{3990,1772},{3991,1505},{3992,188},{3993,2999},{3994,747},{3995,1556},{3996,735},{3997,1934},{3998,750},{3999,2786},{4000,42},{4001,1499},{4002,1358},{4003,1502},{4004,569},{4005,2834},{4006,752},{4007,1503},{4008,317},{4009,1679},{4010,746},{4011,3257},{4012,389},{4013,1503},{4014,1435},{4015,1775},{4016,95},{4017,2558},{4018,998},{4019,1508},{4020,647},{4021,1506},{4022,755},{4023,2961},{4024,189},{4025,2106},{4026,1487},{4027,1511},{4028,416},{4029,2582},{4030,798},{4031,1532},{4032,58},{4033,1506},{4034,755},{4035,2516},{4036,377},{4037,1799},{4038,1262},{4039,1946},{4040,183},{4041,2864},{4042,827},{4043,1524},{4044,632},{4045,1511},{4046,973},{4047,2876},{4048,122},{4049,1517},{4050,1508},{4051,1520},{4052,378},{4053,3257},{4054,761},{4055,1523},{4056,314},{4057,1520},{4058,759},{4059,3407},{4060,483},{4061,1646},{4062,1268},{4063,1535},{4064,48},{4065,2558},{4066,860},{4067,2072},{4068,722},{4069,1520},{4070,896},{4071,2861},{4072,189},{4073,1526},{4074,1637},{4075,1544},{4076,383},{4077,3042},{4078,765},{4079,1530},{4080,155},{4081,2324},{4082,759},{4083,2552},{4084,381},{4085,1772},{4086,1463},{4087,1577},{4088,245},{4089,2663},{4090,761},{4091,1535},{4092,806},{4093,1533},{4094,833},{4095,3724},{4097,1532},{4098,1286},{4099,1538},{4100,374},{4101,2567},{4102,987},{4103,1817},{4104,422},{4105,1533},{4106,768},{4107,2564},{4108,393},{4109,1988},{4110,1280},{4111,1542},{4112,95},{4113,2915},{4114,926},{4115,1545},{4116,857},{4117,1697},{4118,792},{4119,2573},{4120,195},{4121,1539},{4122,1459},{4123,2339},{4124,387},{4125,3044},{4126,774},{4127,1548},{4128,86},{4129,1547},{4130,1028},{4131,3098},{4132,386},{4133,1548},{4134,1286},{4135,1553},{4136,239},{4137,3323},{4138,774},{4139,1553},{4140,796},{4141,1547},{4142,857},{4143,2588},{4144,123},{4145,1548},{4146,1301},{4147,1832},{4148,383},{4149,2938},{4150,794},{4151,2000},{4152,323},{4153,1556},{4154,854},{4155,2591},{4156,390},{4157,1557},{4158,2330},{4159,1560},{4160,18},{4161,2879},{4162,779},{4163,1695},{4164,656},{4165,2066},{4166,782},{4167,2965},{4168,194},{4169,1859},{4170,1322},{4171,1637},{4172,501},{4173,2657},{4174,783},{4175,1581},{4176,184},{4177,1565},{4178,782},{4179,3392},{4180,512},{4181,1562},{4182,1307},{4183,1634},{4184,197},{4185,3279},{4186,1095},{4187,1608},{4188,653},{4189,1670},{4190,788},{4191,3146},{4192,50},{4193,2028},{4194,1487},{4195,1575},{4196,392},{4197,2627},{4198,788},{4199,1736},{4200,419},{4201,1574},{4202,941},{4203,2993},{4204,395},{4205,1566},{4206,1313},{4207,2027},{4208,99},{4209,2858},{4210,783},{4211,1580},{4212,785},{4213,1877},{4214,1097},{4215,2630},{4216,209},{4217,1580},{4218,1457},{4219,1583},{4220,398},{4221,3962},{4222,792},{4223,1613},{4224,26},{4225,1566},{4226,791},{4227,2642},{4228,516},{4229,1584},{4230,1561},{4231,1587},{4232,216},{4233,2714},{4234,788},{4235,2446},{4236,662},{4237,1772},{4238,803},{4239,3120},{4240,93},{4241,1589},{4242,1703},{4243,1592},{4244,396},{4245,2672},{4246,941},{4247,1694},{4248,392},{4249,2055},{4250,782},{4251,2651},{4252,399},{4253,1593},{4254,1328},{4255,1728},{4256,71},{4257,3740},{4258,797},{4259,1598},{4260,683},{4261,1596},{4262,800},{4263,3533},{4264,194},{4265,1593},{4266,1611},{4267,1613},{4268,473},{4269,2672},{4270,1023},{4271,1602},{4272,167},{4273,1601},{4274,800},{4275,3347},{4276,399},{4277,2148},{4278,1547},{4279,1895},{4280,203},{4281,2681},{4282,801},{4283,1607},{4284,977},{4285,1601},{4286,804},{4287,2678},{4288,26},{4289,1607},{4290,1580},{4291,2067},{4292,396},{4293,3200},{4294,890},{4295,1613},{4296,341},{4297,1610},{4298,1043},{4299,2687},{4300,419},{4301,2072},{4302,1537},{4303,1622},{4304,99},{4305,3455},{4306,806},{4307,1670},{4308,677},{4309,1745},{4310,810},{4311,3067},{4312,317},{4313,1805},{4314,1352},{4315,1620},{4316,413},{4317,2702},{4318,821},{4319,2081},{4320,99},{4321,1614},{4322,809},{4323,3248},{4324,459},{4325,1611},{4326,1772},{4327,1623},{4328,201},{4329,3061},{4330,806},{4331,1668},{4332,755},{4333,2096},{4334,959},{4335,2702},{4336,102},{4337,1625},{4338,1538},{4339,1628},{4340,555},{4341,2717},{4342,822},{4343,1703},{4344,338},{4345,1973},{4346,809},{4347,4473},{4348,408},{4349,1629},{4350,1349},{4351,1802},{4352,5},{4353,2726},{4354,1056},{4355,1676},{4356,930},{4357,1632},{4358,818},{4359,2723},{4360,198},{4361,2168},{4362,1367},{4363,1637},{4364,410},{4365,3089},{4366,845},{4367,1934},{4368,218},{4369,1634},{4370,983},{4371,3032},{4372,408},{4373,1638},{4374,1643},{4375,2103},{4376,206},{4377,2741},{4378,980},{4379,1662},{4380,680},{4381,1637},{4382,1055},{4383,3118},{4384,50},{4385,1638},{4386,1439},{4387,1676},{4388,410},{4389,4613},{4390,825},{4391,1647},{4392,388},{4393,1809},{4394,819},{4395,2741},{4396,528},{4397,1647},{4398,1373},{4399,1688},{4400,119},{4401,3284},{4402,903},{4403,2117},{4404,692},{4405,1646},{4406,827},{4407,2750},{4408,227},{4409,1652},{4410,2071},{4411,1955},{4412,414},{4413,2762},{4414,828},{4415,1658},{4416,47},{4417,2136},{4418,864},{4419,3146},{4420,395},{4421,1656},{4422,1688},{4423,1659},{4424,273},{4425,2858},{4426,828},{4427,1835},{4428,818},{4429,1772},{4430,833},{4431,3596},{4432,102},{4433,2090},{4434,1391},{4435,1665},{4436,414},{4437,3140},{4438,1068},{4439,1808},{4440,341},{4441,1664},{4442,831},{4443,2777},{4444,491},{4445,2175},{4446,1742},{4447,1668},{4448,53},{4449,2786},{4450,824},{4451,1670},{4452,893},{4453,1664},{4454,848},{4455,3929},{4456,207},{4457,1670},{4458,1397},{4459,2226},{4460,420},{4461,2792},{4462,908},{4463,1674},{4464,211},{4465,1928},{4466,1271},{4467,2792},{4468,417},{4469,1670},{4470,1391},{4471,1688},{4472,218},{4473,4189},{4474,837},{4475,1694},{4476,698},{4477,2011},{4478,840},{4479,2798},{4480,15},{4481,1679},{4482,1694},{4483,1682},{4484,482},{4485,3041},{4486,842},{4487,2162},{4488,419},{4489,1735},{4490,836},{4491,3197},{4492,422},{4493,1683},{4494,1841},{4495,1788},{4496,104},{4497,2816},{4498,837},{4499,1994},{4500,793},{4501,2177},{4502,845},{4503,3191},{4504,212},{4505,1670},{4506,1412},{4507,1691},{4508,609},{4509,3360},{4510,995},{4511,1700},{4512,92},{4513,1691},{4514,840},{4515,3797},{4516,422},{4517,1692},{4518,1616},{4519,1695},{4520,206},{4521,3344},{4522,1205},{4523,1697},{4524,701},{4525,1686},{4526,902},{4527,3220},{4528,107},{4529,2190},{4530,1433},{4531,1845},{4532,512},{4533,2837},{4534,851},{4535,1703},{4536,545},{4537,1695},{4538,849},{4539,2837},{4540,428},{4541,1898},{4542,1418},{4543,2678},{4544,27},{4545,3214},{4546,851},{4547,1706},{4548,716},{4549,1704},{4550,1086},{4551,2840},{4552,212},{4553,1701},{4554,2075},{4555,1710},{4556,440},{4557,4022},{4558,893},{4559,1781},{4560,197},{4561,1709},{4562,854},{4563,3357},{4564,557},{4565,2072},{4566,1427},{4567,1713},{4568,215},{4569,2861},{4570,851},{4571,2202},{4572,823},{4573,1709},{4574,858},{4575,2849},{4576,62},{4577,1884},{4578,1838},{4579,1898},{4580,423},{4581,3244},{4582,879},{4583,1719},{4584,362},{4585,2243},{4586,858},{4587,3443},{4588,456},{4589,1715},{4590,1688},{4591,1722},{4592,137},{4593,2876},{4594,860},{4595,1725},{4596,722},{4597,1722},{4598,1145},{4599,4190},{4600,231},{4601,1841},{4602,1487},{4603,1727},{4604,432},{4605,2897},{4606,1194},{4607,1739},{4608,7},{4609,2054},{4610,858},{4611,2876},{4612,431},{4613,2231},{4614,1442},{4615,1773},{4616,215},{4617,3827},{4618,864},{4619,1842},{4620,1097},{4621,1731},{4622,867},{4623,3236},{4624,106},{4625,1719},{4626,1640},{4627,2229},{4628,428},{4629,2897},{4630,870},{4631,2051},{4632,362},{4633,1733},{4634,1124},{4635,3346},{4636,479},{4637,1737},{4638,1448},{4639,1740},{4640,48},{4641,3725},{4642,1040},{4643,1742},{4644,899},{4645,1736},{4646,945},{4647,2903},{4648,287},{4649,1742},{4650,1544},{4651,1745},{4652,437},{4653,4064},{4654,881},{4655,2558},{4656,182},{4657,1745},{4658,869},{4659,2912},{4660,431},{4661,1853},{4662,2122},{4663,1749},{4664,257},{4665,2933},{4666,873},{4667,1758},{4668,728},{4669,2445},{4670,878},{4671,3438},{4672,26},{4673,1751},{4674,1619},{4675,2063},{4676,570},{4677,2927},{4678,878},{4679,1755},{4680,409},{4681,1893},{4682,876},{4683,3797},{4684,440},{4685,1751},{4686,1781},{4687,1838},{4688,108},{4689,3323},{4690,1163},{4691,1760},{4692,797},{4693,1954},{4694,881},{4695,2930},{4696,221},{4697,2675},{4698,1751},{4699,1788},{4700,456},{4701,2942},{4702,882},{4703,1764},{4704,122},{4705,1758},{4706,876},{4707,3350},{4708,533},{4709,1760},{4710,1466},{4711,2270},{4712,260},{4713,2951},{4714,882},{4715,1916},{4716,851},{4717,1763},{4718,1136},{4719,3536},{4720,113},{4721,1769},{4722,1481},{4723,1772},{4724,441},{4725,4470},{4726,899},{4727,1793},{4728,368},{4729,1772},{4730,1097},{4731,3353},{4732,567},{4733,1773},{4734,1690},{4735,1778},{4736,12},{4737,2966},{4738,984},{4739,2283},{4740,758},{4741,2111},{4742,890},{4743,3578},{4744,221},{4745,1760},{4746,1907},{4747,1854},{4748,446},{4749,2972},{4750,980},{4751,1782},{4752,263},{4753,2363},{4754,890},{4755,2966},{4756,440},{4757,1889},{4758,1481},{4759,1785},{4760,281},{4761,3679},{4762,891},{4763,2111},{4764,743},{4765,1781},{4766,894},{4767,3866},{4768,54},{4769,1994},{4770,1684},{4771,1797},{4772,446},{4773,3122},{4774,1448},{4775,1806},{4776,377},{4777,1787},{4778,894},{4779,3689},{4780,450},{4781,2312},{4782,1493},{4783,1794},{4784,120},{4785,3530},{4786,896},{4787,1796},{4788,1208},{4789,1794},{4790,900},{4791,2993},{4792,225},{4793,1796},{4794,1562},{4795,2306},{4796,530},{4797,3395},{4798,900},{4799,1800},{4800,44},{4801,1799},{4802,1200},{4803,3002},{4804,449},{4805,1920},{4806,1772},{4807,2561},{4808,224},{4809,3863},{4810,882},{4811,1817},{4812,752},{4813,1803},{4814,923},{4815,3476},{4816,152},{4817,1805},{4818,1784},{4819,1851},{4820,446},{4821,3017},{4822,905},{4823,2319},{4824,443},{4825,1799},{4826,1016},{4827,3017},{4828,464},{4829,2150},{4830,2108},{4831,1812},{4832,57},{4833,3602},{4834,905},{4835,1815},{4836,803},{4837,2339},{4838,938},{4839,3023},{4840,271},{4841,1929},{4842,1714},{4843,1836},{4844,582},{4845,3347},{4846,909},{4847,1844},{4848,188},{4849,1812},{4850,899},{4851,5390},{4852,453},{4853,1997},{4854,1517},{4855,1823},{4856,228},{4857,3041},{4858,1178},{4859,1907},{4860,910},{4861,1821},{4862,1073},{4863,3038},{4864,8},{4865,2378},{4866,1526},{4867,1941},{4868,455},{4869,3448},{4870,915},{4871,1827},{4872,488},{4873,2171},{4874,912},{4875,3032},{4876,495},{4877,1827},{4878,1741},{4879,2348},{4880,108},{4881,3056},{4882,914},{4883,2024},{4884,902},{4885,1826},{4886,1176},{4887,3597},{4888,237},{4889,1832},{4890,1547},{4891,1889},{4892,459},{4893,3932},{4894,918},{4895,2165},{4896,110},{4897,1946},{4898,1002},{4899,3422},{4900,606},{4901,1827},{4902,1778},{4903,1839},{4904,228},{4905,3469},{4906,1097},{4907,2364},{4908,767},{4909,1839},{4910,923},{4911,3068},{4912,116},{4913,1839},{4914,2325},{4915,1845},{4916,459},{4917,3632},{4918,923},{4919,1845},{4920,380},{4921,2621},{4922,1022},{4923,3503},{4924,462},{4925,1836},{4926,1538},{4927,1856},{4928,44},{4929,3278},{4930,905},{4931,1850},{4932,875},{4933,1848},{4934,926},{4935,4133},{4936,230},{4937,1850},{4938,1547},{4939,2189},{4940,506},{4941,3683},{4942,1190},{4943,1854},{4944,197},{4945,2108},{4946,926},{4947,3092},{4948,462},{4949,2460},{4950,2072},{4951,1857},{4952,233},{4953,3143},{4954,927},{4955,1860},{4956,1031},{4957,1857},{4958,956},{4959,3884},{4960,60},{4961,2231},{4962,1556},{4963,2391},{4964,461},{4965,3122},{4966,939},{4967,1863},{4968,498},{4969,1862},{4970,1230},{4971,3107},{4972,551},{4973,1863},{4974,1553},{4975,1881},{4976,117},{4977,4648},{4978,1049},{4979,1875},{4980,797},{4981,1862},{4982,972},{4983,3731},{4984,299},{4985,1863},{4986,1765},{4987,1871},{4988,488},{4989,3122},{4990,938},{4991,2784},{4992,23},{4993,1871},{4994,1118},{4995,3672},{4996,467},{4997,2087},{4998,2072},{4999,1875},{5000,228},};

int main() {
    int n;
    scanf("%d", &n);

    int count = 0;
    for (auto [i, x] : PRECOMPUTED) {
        if (i <= n) {
            count += x;
        }
    }

    printf("%d\n", count);

    return 0;
}