记录编号	126173	评测结果	AAAAAAAAAA
题目名称	[USACO Oct07] 贝茜的秘密牧场	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2014-10-11 16:27:47	内存使用	0.29 MiB

#include <cstdio>
using namespace std;
int main()
{
	freopen("secpas.in","r",stdin);
	freopen("secpas.out","w",stdout);
	int n,a[10001]={1,4,6,4,5,12,12,4,6,16,18,12,8,16,24,12,5,24,30,16,18,28,24,12,12,28,42,28,12,36,48,16,6,36,42,36,29,28,48,28,18,48,60,28,24,60,48,24,8,44,72,48,30,48,84,36,24,52,54,48,36,52,72,52,5,72,96,40,42,72,84,36,30,52,90,76,36,72,96,40,18,88,78,60,60,72,96,60,24,84,150,68,36,76,96,60,12,64,114,96,59,96,120,52,42,120,102,72,68,76,144,76,12,84,144,84,66,124,108,72,48,88,126,96,48,120,192,64,6,124,144,96,84,92,144,120,42,96,168,88,84,120,120,84,29,120,162,128,66,120,216,76,48,156,168,120,84,100,144,108,18,144,210,88,90,168,156,84,60,116,204,160,72,132,216,124,24,132,162,120,138,124,204,124,48,168,228,120,72,208,192,96,8,112,210,192,101,132,264,100,72,172,174,144,120,156,216,156,30,180,312,124,102,168,180,132,84,152,198,172,108,180,264,112,24,244,198,144,132,148,276,192,54,156,330,156,108,196,240,120,36,160,234,208,114,216,288,140,72,204,276,168,156,156,240,216,5,180,288,176,156,252,216,132,96,192,300,192,108,204,408,136,42,248,246,216,168,160,252,208,84,204,312,160,108,288,288,168,30,184,336,220,126,204,384,180,90,288,246,216,200,200,264,204,36,240,414,172,168,244,312,156,96,184,318,348,120,192,360,180,18,276,312,204,209,268,312,220,78,264,456,184,144,280,288,204,60,196,324,264,180,276,444,200,96,312,294,204,180,220,432,280,24,228,408,240,174,312,288,180,150,224,330,292,180,288,408,184,36,348,384,264,204,220,408,312,96,264,528,208,180,316,312,192,12,312,354,316,162,264,552,216,114,300,330,288,252,220,360,320,59,264,456,236,198,420,408,228,120,256,432,312,156,300,528,252,42,316,384,264,312,244,348,312,102,372,504,260,180,384,432,216,68,256,456,384,186,300,468,220,144,440,408,252,228,300,432,300,12,288,672,288,198,340,384,336,144,256,426,408,228,324,600,232,66,432,378,276,306,320,492,316,108,300,540,340,216,408,384,240,48,320,426,408,221,360,624,244,126,388,558,300,264,312,504,468,48,360,528,268,276,384,420,252,192,336,516,392,192,348,696,296,6,448,438,348,300,324,504,348,144,360,618,292,228,556,432,288,84,316,576,444,252,336,600,324,144,396,438,396,360,304,480,364,42,432,744,292,234,496,600,300,168,344,486,480,228,336,696,308,84,480,450,336,312,384,516,484,120,384,768,316,252,432,552,372,29,316,516,436,300,420,636,324,162,624,498,336,356,368,600,396,66,372,816,456,270,436,528,300,216,364,600,472,228,480,648,304,48,528,600,396,390,340,564,504,168,348,660,340,312,576,504,360,84,436,582,504,258,456,996,316,144,484,522,444,324,444,600,468,18,408,696,340,336,576,588,324,210,420,750,560,252,372,744,396,90,544,600,396,456,388,564,504,156,552,834,384,252,484,648,372,60,376,582,676,299,432,744,392,204,516,612,372,420,456,696,460,72,504,912,376,306,696,552,420,216,408,606,528,372,456,888,380,24,648,606,444,372,388,744,520,162,456,936,528,300,528,576,360,138,464,630,508,306,564,864,364,204,628,708,468,372,412,672,684,48,468,882,400,396,632,672,372,228,504,642,600,336,528,1008,376,72,540,696,528,528,412,636,576,192,504,804,464,288,768,648,420,8,448,960,552,306,468,948,496,210,656,630,480,528,492,720,600,101,528,840,424,330,624,768,456,264,464,726,672,300,492,1008,432,72,696,642,504,444,624,756,540,174,504,1194,448,384,580,720,492,120,476,702,788,408,504,888,412,216,828,756,456,468,484,816,556,30,600,888,540,420,688,672,420,312,484,714,600,336,648,1056,532,102,652,906,516,456,460,876,780,180,528,1056,472,396,744,672,432,84,576,786,652,408,576,1128,476,198,700,780,696,468,472,720,588,108,564,1194,460,432,792,720,444,264,560,888,780,336,564,984,540,24,720,714,564,647,564,840,704,198,624,996,472,372,792,1056,456,132,540,798,792,378,588,1128,460,276,676,750,564,576,640,816,676,54,576,1224,612,390,672,780,648,330,532,864,676,444,612,984,504,108,1056,840,504,516,560,1056,636,240,576,1146,600,360,768,768,552,36,548,888,756,402,720,1224,484,234,792,924,576,572,596,840,868,114,552,1056,588,558,808,768,492,288,672,948,816,420,636,1512,496,72,700,912,648,540,544,828,760,276,792,1056,564,420,864,816,540,156,568,1008,748,444,588,1188,720,240,816,822,588,648,580,984,768,5,780,1296,584,438,896,972,516,288,556,996,996,480,624,1080,520,156,804,822,648,642,768,912,700,216,660,1572,556,396,952,912,636,96,656,906,744,516,612,1260,532,300,912,948,660,552,628,1080,936,108,648,1176,724,474,792,1080,588,408,624,882,800,408,864,1176,544,42,964,1032,648,696,580,900,888,246,660,1302,668,588,820,960,552,168,816,1104,888,438,708,1416,612,252,912,906,732,624,604,1032,748,84,732,1344,592,486,1128,912,684,312,616,1164,888,444,708,1560,684,108,820,894,708,768,728,912,832,288,768,1248,644,504,816,1176,576,30,628,1038,1200,491,720,1236,620,336,1024,1044,624,612,768,1080,780,126,816,1704,628,498,936,972,744,384,684,1008,948,540,732,1248,732,90,1008,966,648,768,696,1416,796,246,708,1284,768,552,1100,936,660,200,652,978,840,552,852,1452,648,264,1016,1266,780,612,640,1032,1092,36,708,1512,684,612,1008,1044,612,414,956,1050,844,480,732,1584,616,168,972,1002,912,660,664,1056,960,312,768,1536,708,468,1104,1128,660,96,724,1290,1000,498,816,1512,756,318,900,1068,720,972,752,1056,844,120,984,1368,764,510,1056,1212,672,360,740,1326,1176,540,744,1464,640,18,1064,1002,708,708,816,1140,1092,312,756,1632,700,564,936,1056,912,209,688,1176,916,702,804,1584,652,312,1296,1038,720,660,936,1296,960,78,792,1590,828,648,940,1020,660,456,736,1122,1196,516,972,1632,664,144,996,1512,804,774,764,1176,1080,288,840,1404,776,612,1104,1176,720,60,864,1098,936,534,888,1980,776,324,1056,1086,888,720,768,1248,988,180,864,1440,756,660,1392,1080,684,444,764,1380,988,600,744,1464,936,96,1200,1200,888,888,772,1152,924,294,984,1992,764,552,1012,1320,756,180,848,1284,1320,570,840,1464,700,432,1020,1098,828,840,924,1272,1088,24,816,1824,780,582,1120,1308,852,408,824,1170,1128,672,1020,1632,712,174,1324,1248,804,888,784,1608,1080,288,828,1536,1032,540,1032,1128,720,150,876,1320,1112,605,1044,1548,724,330,1392,1446,804,824,772,1272,1176,180,840,1722,796,732,1060,1236,960,408,936,1278,1096,552,972,2160,736,36,1068,1272,1020,894,896,1200,1080,384,900,1752,784,696,1536,1176,744,204,808,1464,1224,594,816,1788,1008,408,1060,1344,828,936,872,1200,1092,96,1176,1584,852,684,1128,1416,756,528,864,1290,1296,588,948,1800,912,180,1292,1206,804,828,1060,1464,1020,312,996,2220,832,576,1256,1320,924,12,864,1290,1312,888,924,1608,772,354,1320,1266,1080,888,832,1656,1152,162,900,1896,960,654,1260,1296,780,552,992,1380,1080,648,1032,1944,784,114,1132,1488,888,828,1000,1344,1612,330,924,1632,844,768,1272,1416,792,252,1032,1440,1156,618,1068,2040,836,360,1248,1302,1176,960,844,1392,1176,59,972,1878,956,666,1344,1416,804,456,892,1824,1260,684,936,1704,1080,198,1452,1254,900,1146,868,1308,1084,408,1248,1692,856,684,1336,1560,936,120,912,1512,1368,666,936,2292,900,432,1228,1278,924,864,1200,1368,1240,156,1032,2352,944,780,1248,1308,996,528,880,1374,1328,756,1056,1728,832,42,1632,1626,912,876,916,1596,1116,384,1056,2064,1096,684,1280,1320,888,312,928,1404,1464,666,1176,1824,968,348,1236,1734,1008,936,916,1752,1368,102,936,1752,916,930,1612,1428,924,504,1200,1458,1200,756,984,2400,900,180,1252,1350,1296,1056,972,1428,1248,432,1020,2088,892,648,1608,1368,948,68,1192,1680,1204,690,972,1956,1044,456,1324,1488,1032,1104,952,1560,1344,186,1176,2094,904,780,1416,1944,936,468,940,1434,1776,660,1092,1824,880,144,1236,1398,996,1181,1128,1476,1280,408,1128,2280,1200,696,1380,1392,1116,228,964,1656,1248,840,1176,2280,892,432,1824,1500,936,900,976,1776,1300,12,1092,2112,1128,738,1272,1500,1032,672,988,1560,1252,792,1272,2232,980,198,1504,1704,1044,948,1140,1500,1596,384,1080,2082,1032,1008,1324,1416,912,144,1240,1680,1632,714,1080,2304,916,426,1416,1692,1164,1128,1080,1464,1228,228,1176,1896,1016,786,1764,1596,924,600,1016,1926,1320,696,1104,2208,1296,66,1300,1458,1188,1200,1048,1836,1452,378,1272,1968,964,744,1560,1992,936,306,976,1578,1636,864,1044,1956,940,492,1740,1470,1164,948,1320,1704,1368,108,1164,2976,1052,828,1324,1512,1140,540,1136,1644,1468,960,1080,2016,1044,216,1608,1494,1032,1110,1092,1896,1596,384,1068,2304,1188,720,1536,1704,1020,48,1152,1590,1344,852,1656,2196,1008,426,1372,1812,1092,1176,1024,1608,1716,221,1200,2256,1160,948,1368,1524,1020,624,1224,1884,1488,732,1188,2688,976,126,1784,1554,1368,1044,1088,1716,1308,558,1128,2238,1100,792,1704,1584,1128,264,1140,1944,1576,852,1116,2400,1240,504,1428,1620,1128,1404,1196,1560,1324,48,1320,2136,1036,936,1788,1872,1092,528,1072,1662,1968,768,1128,2424,1000,276,1584,2064,1056,1056,1308,1764,1456,420,1368,2544,1048,756,1536,1728,1344,192,1048,1602,1444,948,1260,2100,1228,516,2008,1626,1080,1124,1120,2280,1356,192,1164,2346,1416,858,1640,1584,1020,696,1208,1686,1572,888,1380,2400,1080,6,1476,2046,1284,1248,1084,1896,1656,438,1332,2496,1128,972,1648,1584,1032,300,1512,1722,1560,900,1152,2988,1100,504,1444,1740,1428,1044,1136,1680,1920,144,1224,2160,1084,882,1776,1872,1044,618,1180,2304,1584,816,1464,2184,1260,228,1632,1650,1164,1548,1212,1656,1404,432,1416,2706,1308,864,1640,1992,1056,84,1108,1992,1932,869,1224,2184,1148,576,1752,1650,1248,1224,1488,1776,1420,252,1236,2688,1144,924,1744,1860,1488,600,1120,1734,1584,972,1308,2928,1072,144,2112,1800,1224,1116,1316,2196,1560,438,1176,2280,1368,1080,1512,1824,1152,360,1192,1896,1712,846,1392,2412,1188,480,1756,2352,1260,1092,1200,1824,1860,42,1368,2694,1132,1092,1564,1704,1140,744,1512,1770,1720,840,1380,2736,1256,234,1656,1746,1416,1302,1280,2004,1468,600,1344,2268,1132,900,2352,1752,1104,168,1204,2448,1728,984,1236,2664,1332,486,1564,1746,1416,1392,1168,1992,1820,228,1584,2712,1224,894,1632,2076,1176,696,1488,1782,1872,924,1212,2328,1120,84,1824,1848,1212,1344,1452,1920,1728,450,1344,3228,1168,900,1612,2160,1512,312,1256,1782,1764,1068,1656,2592,1184,516,1920,1980,1200,1452,1228,2136,1516,120,1284,2448,1796,954,1932,1908,1188,768,1204,2088,1560,888,1560,2640,1144,252,1856,2136,1308,1200,1192,2052,2160,552,1272,2400,1396,1116,1824,1776,1368,29,1464,1926,1588,894,1356,3552,1156,516,1824,1980,1500,1212,1400,1968,1548,300,1452,2736,1272,1092,2068,1812,1260,636,1344,2292,2096,972,1272,2472,1404,162,1776,2088,1284,1716,1264,1884,1728,498,1800,2664,1204,924,1980,2352,1176,356,1328,2112,1968,1008,1308,2664,1352,600,1684,1854,1320,1188,1680,2352,1716,66,1464,2952,1264,966,1896,1848,1560,816,1240,2076,1832,1320,1308,2472,1192,270,2232,1890,1608,1236,1300,2304,1596,528,1380,3300,1488,900,1824,2040,1200,216,1500,1926,1848,966,1728,2592,1260,600,1896,2232,1344,1356,1352,2160,2304,228,1320,2760,1308,1278,1956,2148,1212,648,1612,1986,1704,912,1560,3432,1512,48,1684,1926,1596,1488,1276,2028,1768,600,1452,2832,1436,1068,2064,1920,1224,390,1400,2844,1808,954,1500,2556,1476,564,2336,1902,1344,1512,1404,1944,1644,168,1728,2874,1276,966,1804,2616,1416,660,1300,2094,2508,960,1356,2976,1292,312,1812,2076,1464,1536,1800,2220,1660,504,1452,3120,1368,1080,1900,2040,1500,84,1452,1998,2160,1217,1476,2856,1252,582,2136,2256,1404,1464,1448,2424,1936,258,1536,2640,1548,1140,1752,1980,1380,996,1360,2172,1804,948,1800,2712,1524,144,2016,2664,1368,1332,1404,2364,2196,522,1500,2976,1336,1212,2260,2064,1272,324,1608,2232,1936,1242,1488,3432,1276,600,1896,2034,1848,1404,1336,2112,1708,18,1584,3048,1440,1050,2592,1980,1368,696,1568,2460,1800,984,1476,3456,1612,336,1780,1986,1416,1632,1464,2088,2184,588,1848,2760,1448,972,1824,2808,1296,210,1372,2082,2160,1140,1704,2676,1368,750,2128,2034,1500,1584,1620,2136,1920,252,1560,3696,1544,1026,1976,2100,1572,744,1408,2712,2056,1188,1500,2952,1364,90,2640,2256,1440,1506,1512,2556,1756,600,1416,2748,1800,1056,2076,2040,1680,456,1460,2142,1824,1050,1800,3588,1324,564,1900,2610,1608,1512,1592,2136,2340,156,1428,2736,1408,1512,1920,2268,1332,834,1872,2316,2096,1104,1620,3360,1336,252,2340,2400,1800,1380,1408,2304,1920,648,1752,3018,1372,1116,2232,2256,1344,60,1420,2616,2328,1050,1476,2880,2052,582,1992,2232,1440,1916,1556,2472,1944,299,1848,3120,1396,1110,2408,2520,1356,744,1432,2400,2232,1176,1776,3072,1360,204,1972,2106,1632,1428,1804,2364,2040,612,1608,4128,1432,1056,1920,2136,1644,420,1776,2232,2112,1284,1548,2844,1484,696,2568,2178,1536,1380,1504,3024,2112,72,1464,3474,1848,1260,1972,2448,1440,912,1596,2154,2092,1068,2088,2856,1384,306,2136,2616,1632,1944,1488,2388,2356,552,1512,2892,1676,1260,2224,2352,1596,216,1776,2616,1896,1164,1644,3864,1396,606,2388,2376,1920,1464,1456,2232,2028,372,1584,2880,1456,1158,2736,2340,1608,888,1516,2664,1972,1140,1656,3384,1692,24,2164,2178,1536,1800,1888,2412,1884,606,1944,3318,1596,1260,2112,2616,1500,372,1516,2568,3012,1098,1560,3288,1512,744,2028,2622,1512,1560,1812,2352,2072,162,2016,3840,1492,1224,2160,2220,1716,936,1492,2262,2016,1536,1632,3384,1640,300,2400,2274,1560,1488,1640,3192,2340,576,1812,3000,1944,1080,2328,2208,1440,138,1580,2568,2048,1296,1848,3312,1444,630,2400,2886,1836,1476,1632,2376,2328,306,1560,3864,1628,1494,2092,2232,1452,864,2088,2382,2412,1092,1668,3648,1512,204,2028,2376,2088,1721,1528,2292,2240,708,1728,3060,1556,1260,3040,3000,1464,372,1656,2736,2040,1146,1812,3396,1764,672,2232,2472,1644,2052,1656,2328,2200,48,2112,3048,1736,1284,2064,2916,1596,882,1552,2784,2448,1140,1644,3336,1620,396,2712,2274,1560,1752,1848,2484,2112,672,1644,4416,1552,1116,2068,2376,2232,228,1688,2418,2248,1404,1872,3528,1580,642,2496,2334,1680,1692,1896,3144,1996,336,1704,3192,1848,1392,2404,2304,1500,1008,1624,2568,2736,1128,1980,3456,1568,72,2328,3264,1632,1548,1680,2628,2652,696,1872,3096,1552,1440,2256,2352,1512,528,2164,2580,2092,1170,1860,3816,1736,636,2320,2520,1932,1728,1576,2904,2028,192,1776,3708,1692,1266,2976,2388,1668,804,1612,3102,2424,1344,1704,3192,2016,288,2124,2616,2064,2172,1624,2436,2044,648,2064,3672,1576,1260,2748,2832,1596,8,1832,2592,2688,1218,1776,3792,1540,960,2384,2508,1620,1584,1944,2568,2600,306,1668,3912,1752,1242,2208,3096,1860,948,1724,2490,2188,1488,1968,3528,1620,210,2976,2430,1788,1872,1648,3000,2232,630,1836,3546,2232,1320,2140,2400,1560,528,1684,2784,2352,1356,2148,3288,1620,720,2544,2916,1752,1800,1760,2616,2880,101,1740,3216,1688,1476,2488,2448,1800,840,2160,3030,2160,1212,1884,5016,1656,330,2212,2616,2016,1680,2088,2496,2548,768,1824,3576,1636,1368,2640,2472,1584,264,1696,3072,2528,1332,1800,3468,1984,726,2448,2796,1956,1968,1756,2592,2124,300,2616,3792,1636,1290,2284,3312,1596,1008,1712,2622,2928,1296,1872,3624,1832,72,2448,2478,1668,1866,2004,2940,2140,642,1848,3984,1920,1392,2976,2544,1932,444,1660,2586,2400,1776,1800,3600,1764,756,2908,2538,1932,1620,1720,3456,2340,174,1848,4272,1980,1314,2448,2484,1680,1194,1976,2562,2352,1260,2304,3408,1728,384,2636,3360,1812,1668,1732,2676,3072,720,1740,3714,1684,1476,2308,2904,1764,120,2040,2808,2764,1356,2052,4032,1636,702,2292,2550,2196,2244,1800,2808,2188,408,1992,3408,1992,1326,3072,2748,1740,888,2160,3648,2256,1236,1848,3864,1980,216,2648,2700,1812,2316,1756,2880,2392,756,2136,3744,1708,1284,2352,3096,2112,468,1732,2742,3072,1314,1896,3936,1660,816,2760,2784,1764,1668,2564,2640,2220,30,1896,4632,1756,1626,2544,2592,2160,888,1800,2658,2952,1548,2028,3456,1672,420,2808,3000,1740,1968,1872,3372,2236,672,2040,3840,2280,1260,2584,2760,1680,312,1756,2712,2496,1355,2256,4464,2128,714,2332,3156,1812,1728,1768,3120,3120,336,2052,3456,1856,1746,2904,2760,1800,1056,2112,2742,2332,1596,1848,4200,1696,102,2880,2706,2472,1788,1820,2724,2496,906,2076,4524,1812,1428,2880,2856,1704,456,2096,3576,2560,1314,1836,3552,2052,876,2520,2634,2016,2340,2004,2856,2624,180,2316,3576,1836,1386,2800,3696,1776,1056,1792,2976,2856,1332,2064,3864,1820,396,2552,2706,1980,2088,2352,2760,2496,672,2028,4632,2232,1296,2400,2976,2076,84,1816,3480,2380,1620,2016,3564,1732,786,3864,2682,1848,1880,1828,3360,2520,408,1944,3966,2260,1536,2576,2808,2052,1128,1864,2754,2764,1428,2496,4176,1908,198,2532,3216,1884,1974,2096,2856,2808,780,1992,4008,1816,1944,2736,2856,1824,468,2208,2946,2736,1350,2196,5232,1756,720,2452,3132,2400,1764,1852,2784,2808,108,2184,3624,1940,1446,3096,2916,1764,1194,1852,3348,2688,1344,1980,4008,2448,432,2784,2880,1908,2232,1888,3600,2364,720,2352,4014,1828,1332,3108,3432,1836,264,2232,2886,3264,1584,1884,3648,1780,888,2604,2988,2172,2232,2376,2976,2520,336,2052,5280,1876,1524,2680,2796,2604,984,2196,2802,2472,1620,1944,4080,1792,24,3024,3048,2040,2064,2000,3408,3200,714,1920,3768,2208,1524,2736,3168,1860,647,2072,2850,2500,1536,2736,3708,1804,840,2796,3546,2052,2112,1888,3120,2904,198,1992,4272,2376,1716,2712,2796,1812,996,2496,3522,2972,1380,2196,4920,1816,372,2856,2952,2244,2118,1888,3096,2428,1056,2220,3732,1876,1368,3444,2832,2088,132,2016,3690,2544,1548,2160,4920,2376,798,2712,2952,2004,2280,2180,2904,2964,378,2352,4176,2000,1644,2592,3420,1836,1128,1924,3288,3632,1380,1944,3768,1988,276,2908,3264,1980,1908,2568,3072,2460,750,2544,5064,1924,1572,2548,2880,2220,576,1912,2970,2904,1818,2124,3840,2212,816,3456,3132,2112,2028,1984,4056,2476,54,2112,3864,2316,1506,3300,3372,1860,1224,1988,2958,2736,1752,2544,4560,1864,390,2856,3456,2520,1920,1924,3048,3276,780,2136,4392,1936,1944,2832,2880,1980,330,2664,3042,2572,1470,2136,4836,2128,864,2944,2922,2376,1932,2260,3024,2880,444,2124,4800,1980,1554,3144,3348,1884,984,2032,4008,2892,1512,2592,4248,2356,108,2604,2910,2076,2976,2084,3108,2744,840,2424,3996,2216,1452,2896,3528,2016,516,2008,3504,3552,1596,2076,4224,1980,1056,3032,2922,1992,1908,2388,3432,2904,240,2256,4728,2036,1530,2808,3000,2640,1146,2148,3204,2816,1752,2196,4896,1912,360,3888,2970,2112,2208,2312,3588,2556,768,2052,4608,2592,1656,2644,3144,2100,36,2160,3204,3284,1541,2484,4056,1924,888,2748,4584,2076,2160,2008,3144,3096,402,2592,3984,2112,1884,3552,2976,1932,1224,2400,3042,2664,1452,2280,5328,2280,234,2668,3312,2640,2232,2032,3552,2808,924,2160,3960,2172,1548,3792,3168,2196,572,2056,3768,2740,1716,2196,4464,2520,840,3004,3006,2376,2604,2136,3120,2604,114,2784,5208,1996,1530,2812,3960,1956,1056,2536,3312,3696,1668,2088,4056,1960,558,2724,3144,2100,2238,2584,3492,3456,768,2232,4872,2032,1476,3300,3480,2364,288,2120,3384,2952,1860,2436,4536,1972,948,3288,3114,2076,2352,2256,3888,2860,420,2220,4104,2808,1692,2712,3036,2052,1512,2256,3588,2692,1488,2808,4152,1984,72,3680,3672,2412,2028,2136,3276,3348,912,2232,5040,2208,1848,2860,3360,2280,540,2472,3270,2976,1542,2292,5904,2156,828,3072,3090,2760,2280,2360,3120,2816,276,2220,4416,2080,2136,3636,3096,2004,1056,2228,3840,3192,1644,2136,4656,2664,420,3056,3678,2124,2496,2200,3180,3000,816,3216,4608,2068,1620,3000,4152,2100,156,2168,3234,3312,1578,2364,4164,2312,1008,3108,3276,2280,2100,2556,3912,2880,444,2244,5820,2092,1602,3200,3156,2436,1188,2092,3210,3456,2160,2352,4152,2160,240,3456,3384,2520,2298,2324,4320,2880,822,2208,4824,2584,1608,3184,3144,2040,648,2736,3480,2784,1602,2808,4656,2108,984,3000,3768,2244,2304,2128,3528,4368,5,2280,4272,2140,2082,2880,3588,2244,1296,2616,3258,2888,1704,2628,5064,2056,438,3100,3750,2604,2496,2232,3408,2748,972,2496,4722,2608,1548,3888,3192,2064,288,2176,4488,3432,1590,2304,4656,2484,996,3264,3198,2184,2868,2232,3456,2764,480,2640,4320,2592,1740,3276,4056,2376,1080,2140,3552,3408,1560,2328,5856,2080,156,3152,3186,2316,2196,3192,3324,3016,822,2532,5184,2252,1848,3120,3264,2604,642,2212,3306,3296,2208,2352,4704,2160,912,4032,4152,2244,2100,2268,3984,3072,216,2568,4686,2568,1710,2908,3276,2520,1572,2212,3612,3168,1608,2796,4368,2408,396,3144,3888,2244,2646,2388,4032,3384,912,2268,4632,2200,1908,3776,3240,2184,96,2948,3486,2880,1872,2352,5796,2116,906,3144,3492,3324,2160,2312,3576,3160,516,2448,5016,2176,1674,3552,3600,2208,1260,2528,4440,3176,1596,2256,4488,2736,300,3540,3270,2340,2640,2236,3360,3420,948,2784,5040,2316,1836,3052,4560,2136,552,2212,3462,4180,1698,2832,4704,2340,1080,2988,3294,2268,2808,2688,3456,2860,108,2484,6192,2528,1788,3432,3528,2580,1176,2260,3828,2976,2088,2856,4800,2324,474,4128,3342,2328,2232,2348,4056,3120,1080,2388,4440,2676,1764,3000,3552,2472,408,2352,3474,3216,1776,3000,5184,2164,882,3704,4020,2436,2324,2564,3792,3684,408,2280,4902,2272,2400,3052,3588,2244,1176,3024,3708,3936,1632,2304,5760,2300,42,3036,3888,2976,2693,2272,3396,2908,1032,2820,4476,2236,1740,4008,3576,2388,696,2472,4488,3192,1674,2400,5160,3124,900,3052,3708,2376,2664,2468,3960,3172,246,2928,4896,2316,1758,3984,4032,2196,1302,2376,3828,3648,1932,2364,4488,2268,588,3520,3552,2856,2292,2724,3600,3192,960,2412,6882,2484,1656,3076,3408,2652,168,2600,3534,3360,2328,2484,4992,2212,1104,3804,3402,2436,2568,2468,4272,3392,438,2856,4584,2724,1818,3696,3888,2328,1416,2392,3450,3048,1836,3264,5712,2224,252,3124,4362,2400,2640,2372,3792,4356,906,2412,4608,2896,2076,3144,3648,2232,624,3000,4512,3052,1722,2592,5496,2376,1032,3960,3438,2940,2244,2608,3504,2988,84,2436,5136,2296,1932,4176,3516,2568,1344,2384,4320,3340,1716,2364,5400,2880,486,3108,3744,2664,3156,2732,3540,3200,912,3120,4740,2332,2052,3552,4608,2436,312,2332,3816,4320,1746,2424,5124,2260,1164,3528,4392,2388,2568,2980,3720,3276,444,2832,5592,2448,1956,3096,3564,2724,1560,2528,3582,3360,2052,2724,4680,2880,108,4104,3534,2376,2340,2452,5460,3192,894,2616,5868,2808,1932,3756,3624,2352,768,2392,3642,3764,2040,3168,4680,2284,912,3228,4212,2784,2496,2520,3720,3844,288,2592,5400,2480,2148,3588,3684,2292,1248,3240,3702,3432,1860,2736,6672,2296,504,3148,3582,2904,2352,2416,4224,3848,1176,2580,5136,2344,1728,3888,4272,2448,30,2652,4320,3408,1782,2760,4740,3024,1038,3796,3546,2616,3504,2392,3624,3264,491,3264,5274,2708,1980,3220,4284,2532,1236,2496,4200,4164,1860,2556,4752,2320,336,4224,3888,2400,2784,2892,3936,3100,1044,2592,6132,2428,1788,3924,3912,3420,612,2404,3924,3192,2172,2676,6072,2332,1080,3888,3642,2652,2340,2976,4416,3480,126,2496,5280,3432,2160,3240,3564,2340,1704,2576,3702,3680,1800,2952,5352,2420,498,3684,4992,2472,2664,2784,3792,3768,972,3144,5550,2504,2232,3244,3624,2352,384,2952,4032,3556,1980,2784,5880,2696,1008,3228,3690,3168,2664,2508,4248,3724,540,2628,4848,2416,1914,5200,3912,2460,1248,2488,4992,3480,2196,2544,5328,2844,90,3268,3840,2868,2928,2712,3744,3744,966,3360,5640,2496,1836,3408,4752,2376,768,2880,3798,3888,1956,2604,5376,2380,1416,3784,3678,2724,2388,2976,3816,3648,246,2772,6576,2648,1902,3464,4728,2976,1284,2640,3714,3792,2208,3072,4872,2392,552,4464,3714,2544,3180,2488,4464,3196,936,2616,5376,3384,1980,3936,3744,2400,200,2572,4398,3288,1854,3180,5640,2880,978,3896,4896,2688,2448,2500,4104,4212,552,2580,5424,2588,2304,3384,3732,3024,1452,3100,4200,3292,1944,2952,7008,2416,264,3744,3738,3084,2808,2876,3900,3228,1266,2688,5418,2568,2172,4416,3768,2508,612,2768,4866,4608,1854,2736,5016,2916,1032,3348,4296,2688,3276,2608,4656,3244,36,3528,5040,2576,1926,3676,4524,2436,1512,2724,3882,4512,1980,2640,5520,3024,612,3436,3738,2688,2832,3072,4452,3640,1044,2712,6000,2636,1836,3864,3792,3240,414,2628,4056,3552,2723,2988,5376,2452,1050,4584,4140,2880,2484,2548,4704,3276,480,2832,7008,3012,1962,3744,3756,2460,1584,3184,4020,3652,1848,3288,5112,2660,168,3624,4968,2676,2766,2548,4020,4608,1002,2604,5052,2796,2592,4060,4320,2472,660,3288,3954,3600,1902,3204,7464,2476,1056,3680,3870,3144,2880,2560,4032,3900,312,3060,5112,2912,2100,4128,4200,2484,1536,2656,5352,3412,2076,2688,5112,3100,468,4280,4032,2868,3120,2748,4152,3648,1128,3168,5622,2548,1980,3580,4632,3072,96,2596,4392,4656,1974,2820,6264,2500,1290,3564,4008,2592,2820,4128,4008,3340,498,2688,6192,2632,2256,3792,4068,3240,1512,2712,4308,3960,2268,2748,6024,2512,318,4396,4440,2832,2580,2748,4716,4004,1068,3096,5256,3312,1980,3648,4224,2520,972,2668,3894,3532,2124,3348,5400,2964,1056,4512,4878,2700,2532,2744,4800,4056,120,2976,5622,2644,2712,3992,3888,2604,1368,3120,4416,3828,2220,2844,6744,2772,510,3744,4128,3888,2976,2608,3972,3388,1212,2892,6540,3072,2016,4632,3912,2544,360,3008,4752,3480,2100,2916,5808,3060,1326,3508,3894,2784,3408,2692,4032,4372,540,3288,5712,2596,2022,3888,5448,2700,1464,2692,4050,4704,1920,3360,5208,2560,18,3996,4248,2796,3048,3432,4512,3420,1002,2952,7392,2996,1992,3720,4296,3360,708,2892,4608,3868,2364,2868,5256,2660,1140,4992,4140,2688,3276,2852,5136,3672,312,2688,5280,3168,2046,4032,3984,3264,1632,2912,4260,3504,1992,3360,6792,2584,564,3676,5304,2796,2664,3032,4368,4836,1056,2856,5328,2656,2736,3936,3960,2664,209,3456,4230,4576,1986,2892,6456,2700,1176,3880,4782,3216,2652,2704,4272,3468,702,3264,6144,2992,2106,4320,4284,2688,1584,2740,4920,4072,1956,3024,5976,3600,312,3744,4002,2916,3636,2916,4656,3484,1038,4020,5832,2704,2028,4620,4800,2616,660,2692,4182,4344,2664,2760,6072,2928,1296,3628,4062,3240,2880,3228,4392,4212,78,3096,7632,2784,2220,3912,4248,3156,1590,3104,4488,3580,2412,2880,5424,2780,648,5304,4110,2844,2700,3048,5352,4032,1020,2760,6006,3376,1980,3676,5112,2640,456,2800,4392,3948,2058,3864,5424,2808,1122,3816,5118,3408,3476,2792,4224,4248,516,2868,5424,3104,2646,4400,4440,2652,1632,3312,4776,3792,1992,2976,7200,2736,144,4752,4086,3300,2772,2936,4176,3960,1512,3096,5424,2752,2268,4632,4152,3048,774,2816,5616,3676,2172,2856,6384,3528,1176,4080,4344,3024,3240,3300,4200,3864,288,3360,6864,2752,2376,3700,5112,2676,1404,2904,4374,5736,2232,3108,5880,2808,612,3756,4680,2880,3054,3552,4296,3580,1176,3624,6648,2844,2160,4144,4200,3432,60,2900,4230,4080,2484,3072,6672,3080,1098,4464,4194,2832,2736,3048,6408,3900,534,2916,5880,3600,2328,4248,4140,2700,1980,3060,4416,3700,2328,3648,5952,2704,324,4216,5016,3300,3072,2764,4404,4572,1086,2928,7080,2788,2520,4112,4152,3240,720,4136,4230,4216,2208,3024,6768,2716,1248,3732,5136,3420,2964,2812,4320,4332,180,2928,5616,2776,2226,5424,4824,2940,1440,2896,5334,4008,2196,3528,6264,3276,660,3984,4206,3012,4080,2948,4236,3952,1080,3552,5712,3504,2052,3816,5040,2736,444,3080,5520,4708,2171,2964,6144,2740,1380,4992,4194,2844,2820,3432,4800,3840,600,3252,7440,3172,2118,3820,4416,3792,1464,2952,4314,4548,2808,3012,6480,2752,96,4536,4266,2892,3378,3308,5616,4032,1200,3024,5700,3372,2472,4144,4392,2760,888,2944,4752,4296,2154,4164,6312,2764,1152,4184,5880,2904,2772,3120,4416,5040,294,3468,6144,2988,2652,3912,4536,2904,1992,3408,4560,3872,2244,3108,7320,3472,552,4128,4350,3816,2868,2884,4932,3960,1320,3252,6384,2872,2268,5328,4920,2940,180,2884,5208,4180,2448,2976,5760,3472,1284,4572,4290,3372,3816,2920,4320,3724,570,3648,7056,2936,2376,4680,5640,2796,1464,3552,4506,4560,2100,3048,6264,3060,432,3916,4290,3156,2892,3696,4584,4680,1098,3144,7920,2972,2316,3888,4920,3372,840,3048,4464,3916,2616,3768,5724,2812,1272,5272,4596,3156,3264,3164,5208,3756,24,3132,6450,4188,2226,3844,4344,2820,1824,2944,5616,4896,2292,3732,5832,2824,582,4488,5430,3012,3174,2920,4980,5040,1308,3000,6144,2944,2556,4776,4632,3240,408,3864,4494,3840,2364,3156,8916,2916,1170,4088,4350,3744,3240,3356,4752,4108,672,3552,5832,2908,2730,4656,4404,3192,1632,3004,5352,4496,2136,3036,6480,3672,174,4480,5568,3084,3804,2968,4428,3804,1248,4104,6414,3128,2232,4320,5280,2856,888,3048,4530,5172,2214,3096,5856,3520,1608,3996,4410,3024,3240,3724,5208,4032,288,3360,7056,3252,2262,5400,4584,3648,1536,2980,4824,3960,3048,3156,7200,2872,540,4776,5130,3432,2952,3028,5976,4356,1128,3324,6744,3528,2160,4176,4392,3108,150,3464,4656,4176,2460,3696,6144,2960,1320,4428,5316,3264,3240,3132,4608,5952,605,3120,6672,2968,2886,4296,5256,2892,1548,3888,4992,4276,2172,3600,7104,2896,330,3996,4554,3912,3888,3528,4836,3868,1446,3240,5916,3380,2256,5472,4512,2904,824,3128,6360,4272,2226,3144,7260,3492,1272,4544,4446,3456,3528,3052,4728,4212,180,3888,6000,3004,2376,4320,5952,3600,1722,3164,4710,4752,2256,3360,6864,2920,732,4980,4680,3072,3012,4128,4788,3900,1236,3240,8742,3052,2880,4012,4536,3516,408,3040,4800,5312,2700,3132,6048,3528,1278,5376,5172,3060,3228,3076,5496,4160,552,3600,6672,3816,2568,4380,4488,2940,2160,3100,4884,4200,2208,4176,6936,3484,36,4376,5904,3192,3036,3168,5280,5148,1272,3096,6048,3240,2880,4680,4872,2952,894,3648,4758,4416,2592,3372,7224,3096,1200,4684,4638,4548,3240,3140,5088,3948,384,3384,7608,3004,2382,5212,4536,2964,1752,3968,5508,4488,2268,3276,6504,3564,696,4092,4530,3180,4416,3392,4740,4544,1176,3984,6204,3188,2232,4576,6864,3252,204,3112,5088,4896,2298,3840,6672,3060,1464,4156,4992,3204,3528,3696,4992,5040,594,3432,7368,3500,2310,4464,4824,3720,1788,3164,5514,4132,3024,3372,6096,3104,408,6456,4764,3084,3060,3180,5712,3996,1344,3384,7170,4056,2328,4204,4608,3432,936,3288,4782,4800,2472,3924,8256,3004,1200,4236,5544,3168,3276,3524,4992,4824,96,3468,6624,3380,3288,4624,4608,3180,1584,3940,5088,4896,2508,3228,8136,3116,684,4180,5304,4056,3144,3124,4716,4836,1416,3816,6576,3076,2268,5520,4704,3024,528,3288,6420,4156,2484,3180,6300,4176,1290,4564,5040,3264,3744,3792,5376,4224,588,3864,6810,3124,2544,5116,5580,3276,1800,3112,4938,5824,2736,3264,6192,3040,180,4236,4698,3984,3671,3768,5148,4060,1206,3396,8784,3136,2328,4680,5160,3888,828,3880,4722,4416,2982,3372,7080,3240,1464,5616,4872,3348,3060,3336,6288,5096,312,3264,6360,3732,2676,4200,5856,3180,2220,3196,4758,4520,2364,4704,6312,3348,576,4800,5640,3252,3624,3196,4812,4920,1320,3684,7668,3632,2772,4488,4872,3072,12,3864,5616,4536,2484,4056,7992,3076,1290,4824,5028,3864,3732,3240,4872,4108,888,3408,6840,3148,2556,5568,4800,3528,1608,3320,5868,4920,2316,3312,8088,4340,354,4464,4734,3444,3816,3680,5208,4600,1266,3888,6432,3312,3096,4320,5712,3192,888,3468,5184,5856,2382,3312,6324,3100,1656,5280,5424,3204,3456,4128,5160,4140,162,3840,8832,3196,2454,4520,5220,4104,1896,3208,4806,4648,2832,3492,6840,3648,654,5388,5328,3468,3522,3256,6744,4352,1296,3456,6420,4032,2340,6024,4752,3312,552,3284,4902,4296,2784,3924,6936,3124,1380,4348,6054,3984,3168,3576,5280,5460,648,3360,7320,3480,2916,4416,4968,3132,1944,4488,5340,4252,2352,3480,8832,3136,114,5040,4830,4116,3228,3280,5160,5376,1488,3660,7062,3296,2460,5160,5544,3144,828,3548,6312,4920,2862,4008,6504,3780,1344,4308,5028,3408,4836,3280,5160,4608,330,4416,6552,3936,2604,4872,5832,3156,1632,3348,6312,5160,2424,3396,7800,3240,768,5268,5064,3288,3576,4548,5064,4940,1416,3360,7776,3524,2376,4344,4872,4368,252,3256,4938,4348,2940,3708,7440,3172,1440,6048,5160,3636,3368,3776,6192,4440,618,3396,7266,4128,2892,4712,5640,3180,2040,3340,4926,5412,2508,4272,6624,3184,360,4872,7296,3552,3648,3304,5028,5616,1302,3840,6492,3292,3336,4768,4896,3444,960,3936,5328,4368,2442,3468,8712,4032,1392,4396,5184,3936,3528,3352,5688,4840,59,3672,7152,3440,2574,6144,4932,3300,1878,3936,6120,4420,2796,3828,6552,3852,666,5208,4926,3972,3936,3340,5724,4284,1416,4344,8928,3268,2412,4468,5904,3300,456,3752,5190,6672,2502,3528,6984,3312,1824,4752,4926,3576,3600,4044,5568,4928,684,3468,8352,3328,2550,4992,5700,3876,1704,3636,5010,4488,3240,4320,7200,3384,198,5328,5136,3480,4188,3340,6108,4680,1254,3504,7344,4832,2520,4728,5208,3840,1146,3412,5760,4396,2490,4200,7104,3500,1308,5648,6576,3432,3252,3416,5472,5208,408,3528,7602,3416,3432,5040,4980,3720,1692,4008,5178,4936,2484,3828,9360,3456,684,4872,5010,4068,3702,4096,5016,4536,1560,3468,6684,3648,2808,6324,5424,3348,120,3508,6264,5136,2640,3492,8244,3924,1512,4492,5700,3696,4008,3560,5088,4732,666,5376,6720,3340,2574,4752,6264,3276,2292,3388,5388,5904,2700,3504,6744,3752,432,5164,5388,3420,3420,4440,6192,4800,1278,3684,8844,3376,2652,5144,5376,4092,864,3400,6312,5364,3504,3528,6696,3420,1368,5472,5292,3924,3720,3732,6168,4760,156,3684,7752,4056,2796,4984,5028,3300,2352,4176,5106,4680,2736,4188,7536,3304,780,4540,6048,3864,3648,3636,5328,6840,1308,3744,6816,3388,2988,4704,6432,3420,528,4368,5262,4612,2538,4152,9216,3500,1374,5484,5400,4164,3888,3388,5112,4428,756,3816,7830,4216,2880,5472,5232,3684,1728,3584,7740,4960,2496,3540,6816,4392,42,5232,5082,3468,4596,3472,5268,4444,1626,4512,7536,3480,2580,5888,6600,3816,876,3424,5496,5664,2586,3912,8544,3340,1596,4992,5496,3636,3348,4776,5232,4836,384,3564,8280,3472,2976,4800,5196,4368,2064,3560,5652,5904,3204,3588,6840,3352,684,6096,5928,3708,3744,3556,6864,4476,1320,4152,7530,4392,2664,4612,5160,3360,312,4152,5238,5244,2651,4524,7392,3972,1404,4644,6228,3660,4272,3484,6744,5400,666,3600,6888,3636,3204,5904,5136,3684,1824,4416,5370,4968,2904,3840,9648,3476,348,4684,5688,4776,3492,3612,5520,4888,1734,3780,8376,3436,2808,6192,5520,3468,936,4016,6336,4808,2610,3876,7020,4216,1752,5184,5178,3624,4104,3580,5400,5760,102,4584,8496,3780,2634,4952,7176,3396,1752,3508,5484,6144,2616,4092,7632,3668,930,4716,5520,3516,4524,4188,5556,4540,1428,4092,8352,4116,2772,5080,5256,4320,504,3720,6024,4680,3504,3948,7608,3412,1458,7112,5274,3516,3480,3544,6432,5760,756,3624,7488,4212,2694,4944,5688,3912,2400,3580,5916,4636,2700,4464,8040,3528,180,5316,6606,4248,3540,4416,5676,5496,1350,3564,7824,3740,3696,4780,5400,3432,1056,4248,5526,5840,2808,3684,8448,3436,1428,4968,6096,4836,3744,4024,5640,4588,432,4320,7416,3496,2742,6744,5868,3528,2088,3616,6960,4752,2616,3852,7848,4752,648,5452,5298,3660,4584,3668,6648,5460,1368,4440,7104,3556,2844,5688,6336,3456,68,3656,5514,5712,3432,3612,7044,4104,1680,5308,5286,4320,3516,4444,5616,4620,690,4212,11520,3672,2706,4756,5340,4440,1956,4088,5454,5304,3132,4020,7704,3564,456,5736,5568,3648,3846,3688,6804,5312,1488,3888,7728,4608,2856,5268,6264,3480,1104,3640,5490,5160,2694,5088,8256,3484,1560,5136,6936,3756,4032,3764,5976,6448,186,3648,7128,4076,3276,5232,5340,3492,2094,4776,6336,5040,2652,3948,8568,3496,780,6272,5784,4392,4008,3580,5484,4668,1944,3672,7818,3696,2808,5808,5712,4788,468,3764,6576,5640,2694,3792,8304,4464,1434,4860,6066,3768,5136,4488,5400,4684,660,4680,7272,3580,3108,5916,6936,3600,1824,3896,5670,6624,2640,3864,8640,3520,144,4852,6192,3660,3588,4356,6012,5460,1398,4608,9096,3948,2844,4824,5448,4536,1181,3640,5490,5288,3252,4056,7920,4040,1476,6312,5430,3732,3840,3712,7632,4716,408,4116,8112,4528,2988,5504,5388,3540,2280,3824,5550,5272,3504,4848,7272,3740,696,5328,6552,4284,3954,3732,5736,6336,1392,3960,8940,3764,3348,5664,5616,3552,228,5304,6720,5064,2742,3756,9600,3836,1656,4852,5538,4452,3624,3996,5544,5928,840,3876,7272,3840,3108,6528,6228,3564,2280,3724,7128,4876,2676,4272,7752,4284,432,5768,5712,4224,5280,3872,5508,4764,1500,4584,8142,4172,2724,4972,7992,3576,900,3864,6666,6576,2766,4092,7296,3580,1776,6288,5466,4320,3900,4392,5760,4780,12,3900,8784,3792,3060,5460,5904,5208,2112,3688,5844,4920,3288,3996,9792,3924,738,6000,5502,3744,3672,4648,6768,5616,1500,3840,8112,4416,3096,4896,5664,3768,672,4004,6048,5700,2790,4944,7452,3604,1560,5772,7584,3816,3660,3736,5736,6384,792,4296,8022,3700,3558,5208,5820,3744,2232,4900,5730,5952,2940,4044,8856,4136,198,4932,5634,4476,4224,3760,7128,5120,1704,4296,7896,3700,2856,7728,5568,3624,948,4092,7392,5040,3306,3816,8988,4356,1500,5256,5868,4680,4788,3840,5664,5400,384,4584,8616,4104,3000,4992,6660,3972,2082,4280,5670,6196,2976,4080,7488,3780,1008,5556,6048,3792,3756,4752,5736,5568,1416,4128,10158,3888,2736,6192,6408,4380,144,3784,5844,5488,3534,4656,7440,3740,1680,5976,6156,3804,4752,3808,7392,4876,714,3912,8064,5856,3000,5584,5616,3948,2304,3832,6492,4992,2748,4944,9072,3888,426,5864,6720,3864,4104,3772,6168,6396,1692,4512,7440,3888,3372,5088,5664,4200,1128,4896,5898,5216,3096,4008,10812,3676,1464,5900,5682,4632,3684,4304,6144,5376,228,4248,8250,3860,3288,6072,5892,3780,1896,3856,7704,6980,2976,3912,7656,4680,786,5100,7008,3960,5040,4324,5736,5184,1596,5304,7548,3840,2772,5616,6816,3900,600,3796,5898,6576,2909,4212,8520,4332,1926,5140,5658,4176,3792,4620,6912,5356,696,4248,10224,3856,3084,5832,6216,4452,2208,3784,5754,5092,3888,4128,7584,4004,66,7776,5952,4416,3780,4440,6972,4956,1458,4032,9540,4524,3384,5360,5664,3828,1200,4376,5868,5508,2910,4668,8304,4068,1836,5568,7110,3936,4356,3996,5952,6912,378,3936,8400,3820,3516,5728,7176,3960,1968,4656,5970,5400,2832,5040,10008,3872,744,5280,5976,5448,4440,3832,5820,5560,1992,4092,8112,4340,2808,6144,6144,3744,306,3964,8016,5568,2850,4068,7668,4500,1578,6924,6024,3948,4760,4232,6648,5208,864,5040,8592,3820,2922,5212,6936,4560,1956,4212,6762,6732,2820,4044,8808,3848,492,5496,5718,3972,4860,5576,6156,5432,1470,3948,9288,4140,3324,5980,5760,4968,948,3904,5838,5928,3840,4068,8400,3980,1704,6264,7392,3864,4104,3988,7320,5460,108,4920,7776,4608,3054,5664,5772,3780,2976,3904,6180,5188,3036,5256,8448,4608,828,5884,7008,3984,3852,3904,6864,6324,1512,3996,8466,4632,3420,6324,6144,3792,540,4896,6114,5784,3312,4164,10512,3796,1644,5220,5874,5688,4224,3984,6192,5400,960,4572,8856,3868,2982,7416,5820,3804,2016,4496,7080,5400,3132,4128,9120,4572,216,5188,6312,4296,4680,4012,6228,6916,1494,5136,8232,4020,2940,5376,8040,4116,1110,4200,6624,6240,3108,4548,8256,3820,1896,6016,5838,3996,4788,5136,5976,5100,384,4176,11190,4496,2982,5260,6096,4596,2304,4600,6840,6108,3492,4260,7776,3920,720,7248,5946,4656,4416,4048,7848,5116,1704,4008,7884,4900,3060,5704,6408,4392,48,3976,6264,5616,3204,5160,10068,3844,1590,5856,7032,4104,3912,4632,6000,7260,852,4188,7824,4012,4632,5640,5880,3852,2196,5064,6162,5984,3024,4464,9576,4212,426,5868,7320,4740,3948,4000,6360,5376,1812,4752,10272,3916,3024,6628,6000,3864,1176,4092,7176,5800,2958,4800,8016,6048,1608,5268,6108,4200,5148,4048,7056,5400,221,4968,7920,4064,3300,7008,7632,4056,2256,3964,6222,7008,3384,4032,8544,3880,948,5888,5982,4572,3960,4824,6756,5616,1524,4416,11136,4208,3060,5424,6768,4836,624,5016,5994,5332,3564,4308,7908,4004,1884,7032,6360,4368,4368,4024,7920,6156,732,4044,8862,4776,3138,5592,6816,4260,2688,4272,6264,6292,2928,5664,7968,4028,126,5688,7944,4248,5112,4292,6108,6264,1554,4236,7980,4568,3960,6528,6000,3912,1044,5044,7632,5328,3168,4356,10992,4032,1716,6128,6018,4884,3924,4236,6192,6188,558,4212,7992,4704,3180,6480,6060,4800,2238,4200,7746,5356,3228,4248,10608,4716,792,6136,5982,4284,4872,4652,6132,5244,1584,5856,9660,4000,3384,5672,7176,4176,264,4072,6504,8328,3300,4128,8736,3940,1944,5760,6900,4044,4536,5160,6192,5760,852,5184,9648,4328,3090,5860,6120,4740,2400,4176,6624,5400,3720,4332,8760,4520,504,7056,6336,4080,4068,4500,8376,5880,1620,4296,8136,4836,3108,6912,6264,3960,1404,4144,6636,5696,3468,5148,8196,3964,1560,6096,7992,5256,3972,4084,6336,6636,48,4248,10590,4332,3708,5572,6972,4392,2136,5592,6492,5836,3024,4260,10296,3976,936,5928,6324,5280,5064,4220,6504,6080,1872,4428,8100,4060,3276,7488,7032,4128,528,4496,7416,5496,3066,5136,8928,5580,1662,5428,6114,4344,5808,4344,6720,5772,768,5112,9072,4728,3126,5472,7896,4092,2424,4132,7272,7152,3000,4572,8592,4220,276,6896,6078,4260,4464,4956,6288,5688,2064,4344,10752,4156,3060,5500,6192,5520,1056,4096,6672,6720,3720,4752,9336,4104,1764,6996,6210,4368,4368,4984,8232,5356,420,4368,8952,4908,3762,6492,6132,4020,2544,4920,6270,6240,3060,5028,9336,4340,756,5668,9096,4320,4512,4120,6312,7020,1728,4872,8760,4156,4032,5544,6408,4404,192,4944,6552,5500,3066,4500,9960,4616,1602,6912,6828,5748,4140,4284,7152,5388,948,4380,8958,4236,3372,8424,6672,4044,2100,4168,7632,6492,3684,4284,8832,4860,516,5556,6198,5208,5759,4168,6372,5624,1626,5088,9552,4600,3108,6684,7416,4056,1124,5128,6378,6648,3150,4284,10080,4248,2280,5596,6432,4188,4068,5704,6960,7040,192,4740,9960,4248,3324,5568,7392,4884,2346,4280,6744,5644,4152,4992,8784,4320,858,7320,6294,4296,4776,4380,7956,6720,1584,4512,9456,5688,3060,5548,6240,4200,696,4348,7968,5992,3420,5496,8328,4084,1686,6480,8040,4212,4536,4584,6672,6820,888,4992,8784,4240,3840,6552,6264,4788,2400,5016,6594,5544,3240,4656,13344,4096,6,5620,6684,5592,4212,4784,6348,5928,2046,4500,8448,4532,3636,6720,6864,4260,1248,4276,7704,7056,3138,4464,8676,5184,1896,6732,7164,4320,4968,4300,6312,5484,438,6312,9258,4400,3726,6080,7644,4116,2496,4204,6696,7632,3288,4356,8400,5184,972,6000,6792,4248,4638,5520,8064,5500,1584,4680,11376,4376,3096,7044,6336,5376,300,4416,6546,5688,4392,4836,9984,4132,1722,7344,6342,4908,4584,4300,7704,5980,900,4332,9720,5236,3222,5976,6348,4392,2988,5396,6612,6144,3300,5256,8472,4144,504,6400,7608,4428,4212,4288,7992,7680,1740,4368,9282,4364,4032,5788,7248,4572,1044,5616,6498,6732,3312,4992,10152,4156,1680,6048,6426,5220,5760,4264,6480,5760,144,4704,9072,5112,3306,7876,6732,4548,2160,4408,9564,5664,3168,4740,9408,5004,882,6536,6936,4476,5136,4520,6684,6292,1872,5328,9312,4500,3132,6696,7992,4776,618,4264,6630,6816,3270,4500,9744,4508,2304,6372,6636,4392,4608,5880,6816,5580,816,4476,11808,4704,4152,5764,6612,5304,2184,4336,6708,7620,3780,4956,9432,4284,228,7584,7344,4320,4674,4468,7776,5596,1650,5472,8604,5400,3264,6432,7656,4332,1548,4520,6498,5712,3516,5424,9516,4808,1656,5764,8034,4776,4212,4452,7656,8424,432,4740,9024,4324,3948,6648,6396,4212,2706,5416,7236,5836,3816,4428,10320,4216,864,6400,6546,5976,4680,5136,6612,5880,1992,4776,10752,4288,3168,7008,6696,4224,84,5328,8838,6472,3222,4476,8760,5400,1992,5748,6438,4872,5676,4420,6648,7168,869,5328,9360,4324,3444,6540,9732,4356,2184,4496,7032,7248,3444,5256,9624,4340,576,6360,6474,4680,5016,5208,6672,6552,1650,5016,10416,4976,3576,6144,6792,5100,1224,4512,7584,5812,4296,4704,9360,4644,1776,9048,6546,4476,4260,4508,8496,5676,252,4440,10536,5640,3366,6216,6516,4872,2688,4432,6666,6252,3276,6372,10512,4264,924,5916,7800,4800,4944,5328,7020,6840,1860,4452,8772,4372,4464,6920,6528,4272,600,5256,6846,7392,3258,4704,12468,4536,1734,5932,8256,5592,4656,4520,7176,6360,972,5160,8688,4336,3450,7008,6648,4620,2928,5184,7932,5932,3216,4512,8736,6200,144,6492,6534,4740,6144,4480,7560,5724,1800,5808,10110,4556,3504,6824,7896,4788,1116,4760,6858,7608,3780,4488,8760,4300,2196,6240,7944,5064,4680,5268,7368,6080,438,4788,12336,4484,3330,7392,6792,5172,2280,5048,6924,6744,3960,4788,9600,4312,1080,7632,6984,4440,4392,4504,8100,7176,1824,4608,8904,5784,3456,5952,7512,4428,360,4552,7008,6080,3354,7056,9744,4324,1896,6704,8250,4680,5040,4692,6816,6936,846,5004,10632,5084,3996,5980,6828,4332,2412,5352,7740,6696,3564,4692,11256,5040,480,6948,6690,5604,4902,4432,6816,6336,2352,4656,8796,4676,3612,7968,6984,5328,1092,4480,8880,5952,3468,4656,11808,5472,1824,6440,6618,4560,5580,5664,7056,6292,42,5496,9000,4444,3864,6024,8664,4512,2694,4492,7014,8160,3312,4764,8856,4360,1092,7488,7866,5376,4476,5644,6768,5820,1704,5664,11652,4468,3420,6216,7392,5244,744,4480,7164,6588,4392,4752,9432,5000,1770,7920,6726,4500,5000,4868,9672,5836,840,4728,8976,5736,3780,7460,6960,4620,2736,4540,7440,6288,3768,5496,9840,4788,234,6344,8040,5400,4824,4664,7308,8680,1746,4740,11664,4480,4056,6096,6672,4392,1302,6216,7224,6192,3660,5448,10776,4500,2004,6540,6726,5472,4404,4820,7032,6720,600,4968,10128,4456,3648,7296,8376,4404,2268,4800,8256,7260,3336,5244,9744,5544,900,6036,6762,4704,6798,4552,7428,6264,1752,5832,9084,5560,3312,6964,8160,4416,168,5056,7872,7776,3461,4656,9744,4420,2448,7040,6714,4716,4992,5688,7056,6396,984,4776,11400,4668,3450,6528,7260,6912,2664,4824,7116,6004,3996,4848,10344,4432,486,8088,8232,4596,4524,5400,8244,5916,1746,4860,10932,5760,3960,6600,7080,4788,1392,4716,6894,7872,3390,5544,9072,4444,1992,6228,9360,4908,5460,4588,6960,7128,228,5568,9024,4944,4374,7188,6816,4620,2712,5952,7296,6072,3600,5040,13392,5440,894,6052,6882,5484,4608,4736,8688,6448,2076,5364,9048,4576,3528,9096,6840,4560,696,4648,8904,6632,4368,4680,9180,5364,1782,6784,7092,5340,5472,4648,7416,6528,924,5784,11472,4740,3450,6560,8496,4476,2328,5240,7914,7944,3360,5184,9144,4912,84,6528,6822,4656,5184,6024,7104,7068,1848,4740,12336,4600,3456,6700,7896,5580,1344,4728,7038,6360,4152,5496,9984,4844,1920,7344,6990,5472,5184,4776,8856,6916,450,5256,9264,6312,3780,6168,7488,4500,3228,4684,7932,6076,3420,5772,9864,4504,900,9096,8880,4704,4620,4600,7176,7224,2160,4776,10272,4860,4536,6560,7416,5160,312,6068,7254,7140,3612,4860,12816,4932,1782,6204,6894,6120,5040,5276,7056,6336,1068,4776,10080,4612,4536,8352,6912,4620,2592,4744,8850,7032,3552,5172,10128,5436,516,6244,7896,4764,5568,5520,7368,7020,1980,6840,9240,4588,3468,6264,8376,4656,1452,4772,7680,8428,3498,5076,9888,5192,2136,6868,7356,4848,4548,5904,9048,6552,120,4920,12192,4672,3558,7112,6984,5832,2448,5076,7002,7048,5268,5100,9696,4552,954,7512,7296,5364,5676,4720,8616,6076,1908,5208,11268,5556,3564,6828,7152,4980,768,5360,7050,6192,3486,6144,11340,4564,2088,6744,9216,5016,4608,4684,7176,9360,888,4740,9408,5392,4308,6960,7992,4704,2640,5904,7524,6220,3432,5628,11712,4576,252,7116,7416,5712,5376,4660,7464,6336,2136,5016,10218,6240,3708,8256,7080,4680,1200,4944,9768,6864,3486,4872,10248,5704,2052,7824,7524,4920,6480,4732,7224,6124,552,6264,9336,4720,3570,6976,8400,5712,2400,4872,7278,7488,4056,5136,11832,4600,1116,6388,7224,4788,5184,6480,7284,7680,1776,4932,11328,4820,4104,6528,7536,5880,29,5144,7872,7136,4236,4908,9912,4824,1926,8832,8088,4764,4668,5292,9336,6552,894,5544,11232,5628,3666,6292,7320,4620,3552,4732,7170,7400,3468,5940,10152,5288,516,6324,9120,5412,5178,5048,8148,7416,1980,4992,9396,4896,4284,8384,7680,4740,1212,6096,7620,6312,4056,5712,12348,4736,1968,6960,7182,6936,4644,4720,7200,6708,300,5124,12240,4708,3996,7632,7200,4788,2736,5432,8688,6752,3720,4800,9600,6588,1092,6904,7086,5232,6036,4944,7224,7104,1812,5856,11628,4848,3780,6744,10368,4656,636,4916,7326,8916,3828,6144,9480,4660,2292,6888,7332,4836,6048,6016,7200,6220,972,5316,11472,5752,3606,7440,7812,5604,2472,4828,8880,6936,4212,5088,10584,4672,162,8832,7194,5184,5136,4840,10464,6760,2088,4968,9528,5688,3624,6456,7200,5472,1716,5640,7512,6364,3606,5904,10992,5400,1884,7392,8556,4980,5184,5920,7584,7812,498,4884,10362,4932,5064,6648,7176,5124,2664,5856,8382,7944,3552,5232,11520,4696,924,6720,9120,5784,5610,4828,7512,6776,2352,6144,9540,4768,3528,9600,7200,4920,356,4904,8688,6456,3876,5016,10596,6480,2112,6632,7668,4920,5760,4912,8376,7000,1008,6864,9720,5232,3666,7464,9168,4716,2664,4816,7800,8400,4056,4992,11328,4720,600,7224,7206,5880,4836,5820,7512,6528,1854,5508,15216,5240,3840,6792,7536,5952,1188,5640,7302,6988,4848,5076,10248,4732,2352,7728,7218,4980,5148,5172,8952,8064,66,4980,9768,5980,3960,7972,8292,4740,2952,5252,7992,6696,3636,6720,11472,4860,966,6580,9528,5016,5544,5292,7680,8268,1848,4968,9648,5928,4680,6504,7272,5544,816,5856,8802,6436,3618,5232,11640,4756,2076,8144,7500,6432,5304,5048,7392,6720,1320,5148,11010,4932,3690,8236,7956,5448,2472,5312,8892,7224,3576,5136,11184,5724,270,7572,7656,5100,6444,5976,7896,6364,1890,6360,10344,4852,4680,7140,9096,4776,1236,5040,8100,9744,3690,5196,11196,5320,2304,6628,8304,4992,4788,5976,7464,6916,528,5928,13104,5196,3774,6504,7344,5952,3300,5000,7446,6848,4368,6048,9768,5628,900,8832,7398,4932,5280,5168,10296,6720,2040,5160,11772,6216,3600,7472,7320,4980,216,4948,7470,7860,4301,6432,9816,5180,1926,6708,9138,5760,5448,4936,9024,7704,966,5196,11160,4924,4920,7408,7776,4812,2592,7632,7494,6528,3780,5148,12960,4816,600,7500,7398,6312,5448,5196,7668,8712,2232,5280,9816,4888,3756,7920,9240,5268,1356,4996,9330,6604,3912,5916,9924,5796,2160,7632,8088,5436,6912,4948,7440,6444,228,6192,11184,5600,3738,7248,8844,5100,2760,5280,8652,9076,3828,5136,9792,4840,1278,7656,7632,5172,5466,6432,8064,6460,2148,5160,13152,5412,3636,7488,7752,6672,648,4972,8208,6864,4650,5412,13608,5024,1986,7992,7776,5304,4944,6136,9000,7644,912,5460,9960,6264,4344,6840,7608,4860,3432,5140,7554,7568,4536,6384,10056,4968,48,7728,10200,5208,4932,4996,7920,8640,1926,6312,10770,4948,4524,7152,7440,4872,1488,6000,8352,7772,3714,5364,13392,5700,2028,6636,7530,5976,5304,5496,9264,6508,600,5364,9912,5360,3894,10272,7920,4884,2832,5044,9060,6672,4236,5304,11256,6696,1068,6700,7494,6432,6000,5044,7764,7072,1920,6600,11496,4960,3672,7392,9864,4896,390,5720,7872,7968,3960,5196,10608,5040,2844,8380,8334,5124,5328,6336,7776,7488,954,5592,13056,5032,4188,6676,8616,6384,2556,5056,7662,7404,4428,6192,10008,5760,564,8436,8052,5256,6816,5044,9156,6840,1902,5232,11040,6864,3804,7264,7536,4920,1512,5576,9432,7056,3996,6864,10920,5060,1944,8004,9366,5196,4932,5148,8424,8880,168,5112,10536,5056,4968,7248,7524,5640,2874,6024,7866,8160,3744,5532,13968,4936,966,7464,7554,6528,5100,6168,8268,6840,2616,5424,11526,5044,4248,8088,7584,4944,660,5976,9912,8396,3774,5544,10848,5940,2094,6804,8850,5400,7344,5140,7728,6604,960,7080,10920,5044,3834,7696,9144,5832,2976,5304,7674,8088,3876,5364,12000,6160,312,6796,8538,5112,5124,6304,8856,7176,2076,5424,12144,5104,4152,8592,7560,5964,1536,5324,7638,6796,5256,5376,10068,5084,2220,10080,7746,6192,4980,5128,9720,6912,504,5400,12912,6648,4092,6868,8172,5208,3120,5888,8208,7800,3960,6192,11256,4984,1080,6828,9120,5760,5514,5128,7992,9920,2040,5676,10164,5412,4500,7668,9312,5100,84,6192,7686,6816,4188,6036,13872,5096,1998,6820,8196,6240,6264,5504,7704,7956,1217};
	scanf("%d",&n);
	printf("%d\n",a[n]);
	return(0);
}