#include<fstream.h>

ifstream fin("fractii.in");
ofstream fout("fractii.out");

int main()
{
	long n,v[100000]={1,3,7,11,19,23,35,43,55,63,83,91,115,127,143,159,191,203,239,255,279,299,343,359,399,423,459,483,539,555,615,647,687,719,767,791,863,899,947,979,1059,1083,1167,1207,1255,1299,1391,1423,1507,1547,1611,1659,1763,1799,1879,1927,1999,2055,2171,2203,2323,2383,2455,2519,2615,2655,2787,2851,2939,2987,3127,3175,3319,3391,3471,3543,3663,3711,3867,3931,4039,4119,4283,4331,4459,4543,4655,4735,4911,4959,5103,5191,5311,5403,5547,5611,5803,5887,6007,6087,6287,6351,6555,6651,6747,6851,7063,7135,7351,7431,7575,7671,7895,7967,8143,8255,8399,8515,8707,8771,8991,9111,9271,9391,9591,9663,9915,10043,10211,10307,10567,10647,10863,10995,11139,11267,11539,11627,11903,11999,12183,12323,12563,12659,12883,13027,13195,13339,13635,13715,14015,14159,14351,14471,14711,14807,15119,15275,15483,15611,15875,15983,16307,16467,16627,16791,17123,17219,17531,17659,17875,18043,18387,18499,18739,18899,19131,19307,19663,19759,20119,20263,20503,20679,20967,21087,21407,21591,21807,21951,22331,22459,22843,23035,23227,23395,23787,23907,24303,24463,24727,24927,25263,25391,25711,25915,26179,26371,26731,26827,27247,27455,27735,27947,28283,28427,28787,29003,29291,29451,29835,29979,30423,30615,30855,31079,31531,31675,32131,32307,32547,32771,33235,33379,33747,33979,34291,34483,34959,35087,35567,35787,36111,36351,36687,36847,37279,37519,37847,38047,38547,38691,39131,39383,39639,39895,40407,40575,41007,41199,41535,41795,42319,42479,42895,43111,43463,43727,44263,44407,44947,45203,45491,45763,46163,46339,46891,47167,47527,47719,48279,48463,49027,49307,49595,49835,50315,50507,51051,51275,51659,51947,52531,52699,53163,53451,53811,54107,54635,54795,55299,55599,55999,56287,56767,56959,57571,57811,58219,58459,59079,59271,59895,60207,60495,60807,61439,61647,62207,62463,62887,63151,63727,63943,64423,64747,65179,65499,66051,66211,66871,67199,67631,67963,68491,68683,69355,69667,70115,70371,70971,71187,71775,72111,72463,72807,73499,73723,74419,74659,75091,75411,76115,76347,76907,77259,77643,77999,78715,78907,79591,79951,80391,80679,81255,81495,82227,82579,83059,83347,83971,84211,84955,85275,85675,86043,86715,86931,87687,87975,88479,88859,89623,89879,90359,90743,91247,91631,92407,92599,93303,93639,94159,94551,95175,95415,96207,96603,97035,97355,98155,98419,99139,99539,99971,100307,101027,101283,102099,102419,102963,103371,104067,104331,104987,105371,105923,106283,107119,107311,108151,108571,109123,109539,110179,110459,111179,111603,112083,112419,113279,113567,114431,114791,115239,115671,116463,116751,117627,117947,118451,118835,119719,120007,120711,121155,121747,122131,123027,123267,124067,124515,125115,125567,126143,126431,127343,127799,128375,128727,129647,129887,130811,131259,131739,132203,133135,133423,134215,134583,135207,135671,136511,136823,137543,137927,138551,139027,139983,140239,141103,141583,142111,142551,143319,143643,144615,145095,145743,146079,147059,147379,148275,148707,149187,149667,150507,150835,151831,152231,152895,153395,154399,154687,155487,155927,156551,157055,158071,158327,159191,159703,160351,160863,161679,162015,162935,163367,164055,164439,165479,165815,166859,167379,167859,168383,169343,169663,170675,171091,171787,172219,173179,173531,174379,174907,175619,176155,176995,177283,178363,178903,179623,180135,180999,181287,182379,182923,183643,184043,185051,185403,186339,186891,187467,188019,189131,189491,190499,190883,191523,192083,193207,193575,194471,195035,195683,196243,197379,197667,198807,199287,200047,200527,201407,201791,202943,203487,204255,204703,205687,206071,207111,207687,208263,208847,210019,210355,211435,211899,212683,213259,214443,214803,215571,216163,216955,217483,218679,218999,220199,220703,221495,222095,222975,223375,224587,225163,225835,226315,227419,227803,229027,229639,230279,230759,231991,232399,233635,234115,234907,235527,236583,236967,237967,238591,239311,239935,241087,241375,242635,243259,244099,244731,245739,246155,247163,247723,248563,249075,250355,250779,252063,252591,253263,253839,255131,255563,256723,257203,257923,258571,259875,260307,261347,261987,262851,263403,264719,265039,266359,267019,267787,268443,269307,269739,270971,271635,272523,273051,274251,274635,275979,276651,277371,277995,279347,279795,280947,281459,282363,282963,284327,284759,285847,286435,287347,288019,289267,289619,290999,291687,292407,293099,294203,294651,295931,296627,297555,298035,299435,299867,301163,301803,302539,303243,304443,304907,306323,306883,307819,308523,309843,310227,311187,311899,312851,313567,315003,315387,316611,317295,318255,318975,320095,320535,321987,322563,323535,324111,325455,325935,327399,328131,328803,329507,330827,331307,332783,333359,334223,334847,336331,336811,337995,338739,339723,340363,341635,342035,343535,344271,345271,345943,347143,347575,349087,349843,350723,351299,352819,353323,354619,355379,356147,356911,358303,358815,360351,360831,361855,362623,364167,364671,365871,366639,367503,368279,369719,370103,371503,372207,373215,373887,375135,375655,377227,378011,379059,379683,381027,381507,382947,383739,384571,385363,386955,387387,388859,389499,390555,391355,392795,393323,394379,395099,396171,396971,398587,399019,400639,401311,402391,403111,404407,404919,406431,407247,408111,408751,410391,410935,412579,413395,414195,414891,416543,417071,418727,419383,420487,421255,422599,423151,424479,425199,426279,427115,428791,429175,430799,431639,432759,433599,434847,435399,436719,437551,438679,439319,440903,441463,443167,443887,444751,445599,447311,447791,449507,450179,451139,451999,453723,454299,455675,456539,457627,458347,459907,460355,461939,462803,463955,464747,465947,466523,468275,469151,470319,470959,472719,473223,474987,475755,476683,477567,479339,479915,481427,482131,483211,484099,485755,486347,487771,488539,489595,490491,492171,492651,494315,495115,496123,497019,498459,499059,500871,501775,502975,503551,505371,505947,507587,508499,509459,510371,511931,512507,514343,515047,516271,517191,518871,519351,520791,521715,522939,523835,525691,526171,527683,528611,529851,530783,532063,532639,534511,535303,536551,537287,539167,539791,541551,542479,543343,544183,546075,546699,548427,549147,550411,551179,553083,553707,555227,556179,557299,558255,559887,560399,562259,563123,564395,565355,566891,567419,569351,570231,571383,572151,574091,574739,576395,577367,578327,579287,581239,581887,583647,584319,585615,586595,588559,589199,590767,591663,592767,593631,595479,595959,597939,598899,600219,601059,602643,603299,605291,606287,607583,608383,609823,610487,612343,613343,614399,615403,617275,617851,619867,620667,622011,622891,624915,625539,626883,627891,629235,630251,632287,632799,634839,635703,636903,637927,639527,640175,642047,643071,644247,645063,647123,647795,649859,650779,651835,652699,654619,655307,657383,658151,659535,660575,662351,663023,664463,665507,666899,667939,670035,670515,672615,673663,674959,675919,677599,678239,680039,681051,682459,683291,685411,686107,688231,689095,690215,691175,693095,693799,695935,696783,697935,698991,701007,701719,703399,704471,705903,706743,708711,709287,711311,712391,713759,714839,716279,716999,719171,720195,721515,722379,724559,725135,727319,728411,729563,730651,732843,733563,735435,736235,737699,738707,740911,741615,743151,744087,745527,746631,748847,749423,751423,752527,753775,754887,756663,757383,759615,760623,762111,762879,764967,765607,767851,768971,770171,771295,773143,773879,776135,777031,778375,779503,781543,782191,783999,785119,786631,787767,789879,790455,792399,793539,795051,796011,797835,798595,800755,801715,803243,804123,806423,807191,809495,810647,811607,812695,814807,815575,817735,818631,820143,821127,823451,824219,826075,827115,828667,829819,831811,832387,834727,835895,837303,838475,840315,840987,843107,844187,845747,846675,849035,849819,851691,852843,854091,855275,857647,858367,860607,861375,862959,864143,866527,867319,869223,870279,871575,872771,874931,875571,877971,879171,880771,881779,883699,884491,886731,887931,889371,890251,892315,893115,895539,896751,898047,899199,901631,902303,904591,905551,906991,908095,910539,911307,912987,914211,915843,917067,919523,920163,922623,923583,925215,926447,928175,928991,931463,932699,934091,935051,937355,938147,940387,941627,942939,943995,946347,947115,949611,950611,952267,953515,955651,956371,958371,959619,961291,962443,964959,965535,967839,969099,970779,972027,973787,974627,976787,978051,979707,980715,983115,983947,986323,987331,988611,989731,992283,993123,995679,996703,998143,999423,1001987,1002835,1004883,1006167,1007607,1008663,1011239,1011911,1014491,1015643,1017363,1018655,1020383,1021247,1023839,1024999,1026727,1027687,1030287,1031007,1033611,1034907,1036251,1037555,1040167,1041031,1042951,1043991,1045575,1046855,1049255,1050119,1052215,1053319,1055071,1056387,1059023,1059663,1062303,1063623,1065135,1066455,1068535,1069303,1071955,1073267,1075035,1075899,1078319,1079183,1081703,1082935,1084343,1085671,1087951,1088839,1091287,1092343,1094119,1095319,1097815,1098583,1100727,1102071,1103863,1105207,1107727,1108447,1110751,1111999,1113599,1114951,1117111,1118007,1120559,1121711,1123511,1124535,1127255,1128159,1130735,1131935,1133087,1134451,1137183,1138047,1140711,1141799,1143623,1144799,1147543,1148455,1150455,1151799,1153527,1154775,1157127,1157831,1160591,1161971,1163811,1165187,1167395,1168115,1170707,1172091,1173939,1175043,1177587,1178483,1180859,1182139,1183579,1184971,1187491,1188419,1191215,1192175,1194039,1195439,1198079,1198943,1201183,1202479,1204063,1205343,1208159,1208895,1211519,1212927,1214799,1215999,1218255,1219183,1221775,1223191,1224871,1225991,1228343,1229279,1232123,1233531,1234971,1236291,1239143,1239911,1242767,1243727,1245599,1247023,1249887,1250839,1252759,1254191,1256103,1257539,1260415,1261183,1263783,1265007,1266735,1268103,1270279,1271239,1274131,1275571,1277155,1278275,1281175,1282055,1284959,1286411,1287947,1289099,1291859,1292831,1295747,1296899,1298843,1300187,1302347,1303307,1305643,1307107,1309051,1310515,1313203,1313875,1316815,1318223,1320183,1321503,1323823,1324783,1327303,1328779,1330571,1331723,1334683,1335547,1338511,1339759,1341199,1342683,1345655,1346615,1349591,1350775,1352455,1353943,1356927,1357911,1360023,1361303,1363295,1364567,1367563,1368363,1371171,1372671,1374663,1376135,1378151,1379151,1381871,1383215,1385223,1386423,1389443,1390307,1393123,1394635,1396235,1397747,1400627,1401507,1404027,1405179,1407051,1408571,1411615,1412623,1415023,1416319,1418351,1419871,1422631,1423399,1426459,1427987,1429715,1431107,1433555,1434579,1437491,1439027,1440971,1441931,1444835,1445859,1448943,1450479,1452111,1453655,1455959,1456967,1460063,1461263,1463103,1464639,1467743,1468607,1471087,1472639,1474703,1476143,1479259,1480027,1482691,1484091,1486171,1487579,1490075,1491083,1494215,1495559,1497647,1498895,1502035,1503075,1505715,1507287,1508727,1510295,1513247,1514295,1517451,1518699,1520619,1521963,1525127,1526087,1528615,1530055,1532079,1533663,1536375,1537207,1540231,1541815,1543903,1545495,1547735,1548599,1551791,1553263,1555183,1556463,1559663,1560719,1563455,1565055,1566751,1568191,1571403,1572459,1575675,1576731,1578867,1580307,1583531,1584603,1586907,1588507,1590187,1591803,1595039,1595903,1599143,1600763,1602923,1604267,1606667,1607747,1610999,1612439,1614599,1615895,1618679,1619703,1622783,1624295,1626023,1627655,1630927,1631791,1634751,1636031,1638215,1639855,1642975,1644063,1646271,1647915,1650075,1651707,1654779,1655579,1658603,1659995,1662011,1663663,1666303,1667359,1670671,1672327,1674199,1675511,1678511,1679615,1682939,1684475,1686203,1687547,1690879,1691983,1695319,1696647,1698871,1700311,1703167,1704247,1706887,1708559,1710575,1712251,1715419,1716187,1719467,1721091,1723011,1724691,1727379,1728499,1731379,1733059,1735307,1736555,1739723,1740827,1744211,1745531,1747323,1748987,1752379,1753507,1756903,1758183,1760127,1761711,1764831,1765951,1768351,1770055,1772327,1773767,1777183,1778047,1781295,1782991,1785271,1786983,1789335,1790295,1793495,1795211,1797491,1798835,1802275,1803235,1806679,1808399,1810159,1811883,1815003,1816155,1818747,1820123,1822427,1824155,1827619,1828707,1831475,1832915,1835219,1836779,1840091,1840987,1844467,1846051,1848019,1849747,1852531,1853683,1857175,1858759,1860839,1862039,1865303,1866455,1869959,1871711,1873439,1875191,1878191,1879359,1882875,1884155,1886499,1888259,1891619,1892627,1895443,1897207,1899367,1900903,1904263,1905191,1907831,1909599,1911951,1913723,1916523,1917675,1921227,1922739,1925107,1926515,1929779,1930859,1934423,1936199,1937735,1939391,1942963,1944147,1947723,1949147,1951523,1953059,1956299,1957355,1960219,1962011,1964403,1966083,1969155,1970115,1973715,1975379,1977779,1979379,1982115,1983123,1986435,1988227,1990603,1992043,1995663,1996863,1999887,2001699,2003459,2005267,2008699,2009899,2013291,2014443,2016867,2018687,2022331,2023483,2026363,2028003,2030019,2031843,2035323,2036283,2039943,2041767,2043975,2045535,2048463,2049615,2052935,2054771,2057219,2058627,2061771,2062995,2066451,2068291,2070211,2071891,2075583,2076543,2080155,2081595,2084059,2085907,2089363,2090587,2093083,2094875,2097347,2099203,2102323,2103283,2107003,2108515,2110891,2112747,2115723,2116963,2120695,2122559,2124671,2125951,2129691,2130843,2134587,2136459,2138459,2140043,2143795,2145043,2148799,2150271,2152431,2154311,2157527,2158775,2161463,2163223,2165527,2167383,2171159,2172023,2175623,2177303,2179823,2181715,2184739,2185987,2189227,2190955,2193475,2194915,2198715,2199979,2203419,2204955,2206971,2208875,2212687,2213935,2217543,2219063,2221079,2222983,2226807,2227927,2230983,2232895,2235415,2237047,2240647,2241671,2245255,2247115,2249675,2251403,2253803,2255075,2258755,2260675,2263243,2264779,2268639,2269695,2273559,2275491,2277507,2279267,2282819,2283971,2287283,2288819,2291403,2293343,2297039,2298335,2301439,2303095,2305415,2307359,2311255,2312215,2316115,2318035,2320195,2322147,2324963,2326259,2329931,2331691,2334299,2335643,2339387,2340683,2344283,2346243,2348323,2350287,2353647,2354927,2358487,2360055,2362647,2364439,2368383,2369487,2372607,2374335,2376967,2378815,2382771,2383731,2387115,2389095,2391735,2393655,2396823,2398143,2402115,2403795,2406099,2407683,2411283,2412595,2416579,2418571,2420299,2422291,2426283,2427579,2431575,2433175,2435639,2437079,2441083,2442411,2445611,2447467,2450131,2452131,2455491,2456547,2460567,2462575,2464975,2466847,2469727,2470879,2474911,2476927,2479615,2481215,2485079,2486423,2489687,2491447,2493607,2495631,2499683,2500931,2504987,2506331,2509035,2511051,2514867,2516211,2519091,2521123,2523427,2525463,2529539,2530563,2534307,2536347,2539059,2540787,2544051,2545251,2549123,2551171,2553899,2555499,2559003,2560299,2564403,2566275,2568451,2570499,2574019,2575195,2579115,2580747,2583483,2585543,2589667,2591011,2593795,2595859,2598355,2600195,2604331,2605387,2609275,2611003,2613763,2615683,2618963,2620339,2624299,2626375,2628535,2630071,2634231,2635615,2639779,2641859,2644067,2645843,2650015,2651359,2655535,2656975,2659535,2661623,2664791,2666183,2669527,2671607,2674391,2676487,2680683,2681643,2685443,2687543,2690343,2692439,2695799,2697095,2700623,2702543,2705135,2706815,2711035,2712315,2716539,2718339,2720547,2722571,2726603,2728011,2731899,2733563,2735963,2738083,2741923,2743315,2746515,2748639,2751471,2753199,2757455,2758575,2762835,2764755,2767563,2769483,2772363,2773771,2778043,2780179,2782819,2784515,2788795,2789947,2794231,2796343,2798263,2800279,2804311,2805735,2809407,2811087,2813943,2816087,2820391,2821823,2825263,2826943,2829815,2831783,2835815,2836967,2841287,2843311,2845759,2847919,2851375,2852743,2856663,2858823,2861703,2863143,2867127,2868567,2872727,2874899,2877139,2879187,2882907,2884227,2888583,2890311,2893215,2895395,2899571,2900723,2903891,2906075,2908991,2911175,2915135,2916287,2920031,2922207,2924895,2927087,2930591,2932031,2936087,2937959,2940887,2942487,2946687,2948151,2952555,2954571,2956587,2958791,2963203,2964611,2968935,2970471,2973111,2974983,2979407,2980847,2984383,2986591,2989543,2991759,2995551,2996703,3001143,3003143,3005735,3007943,3011463,3012711,3016871,3019095,3022063,3023839,3028063,3029503,3032863,3035095,3037463,3039479,3043951,3045439,3049915,3051451,3054403,3056491,3060975,3062255,3065839,3068083,3070627,3072867,3076995,3078195,3082695,3084943,3087943,3089791,3092991,3094463,3098783,3101039,3104039,3105831,3109287,3110631,3114951,3117207,3119607,3121647,3126179,3127475,3132011,3133819,3136843,3139083,3143627,3145139,3148019,3150291,3152931,3155043,3159411,3160563,3165123,3167067,3170107,3172387,3176035,3177547,3182119,3184039,3186631,3188455,3192823,3194343,3198927,3201087,3203391,3205311,3209903,3211431,3215391,3217151,3219935,3222235,3226099,3227635,3231315,3233619,3236691,3238995,3243611,3244571,3249191,3251367,3254439,3256551,3260247,3261783,3265743,3267903,3270991,3272783,3276983,3278495,3282895,3284863,3287263,3289587,3293859,3295395,3299747,3301603,3304195,3306275,3310939,3312491,3316219,3318523,3321403,3323395,3328071,3329223,3333903,3336243,3339043,3341379,3344547,3345955,3350647,3352991,3356015,3357855,3362555,3363899,3368219,3370339,3372835,3374995,3379707,3381267,3385299,3387155,3390299,3392659,3397075,3398643,3402003,3403875,3407019,3409323,3413811,3415059,3419799,3422167,3424855,3427227,3430827,3432267,3437019,3439259,3442139,3443675,3448435,3450019,3454783,3457151,3459647,3462031,3465631,3467215,3471991,3473895,3477079,3479191,3483975,3485271,3489095,3491487,3494431,3496591,3501387,3502667,3506783,3509183,3512351,3514751,3518207,3519807,3524399,3526415,3529295,3531215,3536035,3537619,3542155,3544395,3546507,3548907,3553739,3555179,3559819,3561579,3564795,3566859,3571703,3573303,3577143,3579567,3582799,3585223,3589375,3590671,3594511,3596815,3600055,3602487,3606375,3607719,3612591,3614879,3618119,3620039,3624919,3626359,3630535,3632743,3635335,3637779,3642671,3644207,3648887,3650567,3653591,3656039,3660479,3662111,3666031,3668479,3671071,3673527,3678443,3679723,3684387,3686847,3690127,3692047,3695631,3697263,3702195,3704659,3707947,3709675,3713899,3715531,3720475,3722947,3725347,3727819,3732771,3734163,3738915,3740835,3744139,3746443,3751003,3752587,3755947,3758187,3761499,3763979,3768659,3769971,3774755,3776867,3780179,3782531,3786515,3788051,3792571,3795067,3797755,3799755,3804555,3806211,3811215,3813711,3816367,3818503,3823255,3824695,3829303,3831303,3834543,3837039,3841335,3843007,3847023,3849327,3852679,3855195,3859755,3860907,3865947,3868251,3871499,3874019,3878019,3879699,3883803,3886299,3889659,3891419,3896479,3898159,3902895,3905055,3907551,3910079,3914951,3916607,3921683,3923699,3926339,3928739,3933823,3935487,3939551,3941927,3945311,3947327,3952423,3953703,3958803,3961043,3964211,3966763,3970219,3971899,3977011,3979567,3982975,3985023,3989727,3991167,3995807,3998367,4000959,4003523,4008323,4010019,4014411,4016459,4019883,4022451,4027371,4028811,4032891,4035003,4038435,4041011,4046167,4047511,4052439,4055019,4057899,4060203,4063883,4065603,4070355,4072939,4076387,4078115,4083295,4085023,4090207,4092799,4095551,4097871,4102239,4103967,4108895,4110815,4114079,4116679,4121575,4123015,4127175,4129779,4132899,4135491,4140707,4142051,4146515,4149123,4152291,4154903,4159079,4160807,4166039,4167959,4171415,4173495,4178735,4180319,4185359,4187919,4190319,4192719,4197759,4199487,4204247,4206343,4209847,4212055,4217319,4219071,4222911,4225543,4229047,4231683,4235715,4236995,4241963,4244603,4248123,4250763,4254811,4256323,4261615,4264255,4267783,4269863,4274663,4276199,4280735,4283387,4286171,4288795,4294107,4295875,4301191,4302919,4306463,4308883,4314207,4315935,4319775,4322295,4325319,4327783,4332775,4334183,4339523,4342179,4345419,4347699,4351939,4353715,4359067,4361515,4364827,4366939,4371523,4373299,4378663,4381063,4383911,4386407,4391779,4393315,4398691,4400835,4404003,4406691,4412075,4413867,4417227,4419915,4423275,4425795,4431191,4432631,4437815,4440119,4443447,4445943,4450263,4451863,4457275,4459979,4463003,4465163,4470583,4472375,4477799,4480351,4483231,4485535,4489855,4491655,4497091,4499139,4502763,4505483,4510139,4511947,4516267,4518843,4522443,4524843,4530299,4531451,4536911,4539639,4543279,4546011,4550379,4552107,4556331,4558995,4562275,4564451,4569931,4571755,4576795,4579147,4582027,4584771,4590051,4591875,4597371,4599371,4602491,4605179,4610683,4612411,4616443,4618939,4622611,4624963,4630243,4631651,4636651,4639411,4643083,4645843,4649587,4651427,4656959,4659711,4663071,4665279,4670463,4671903,4677239,4679831,4682711,4685479,4691031,4692879,4697631,4699839,4703511,4706055,4710895,4712687,4717135,4719511,4723223,4725783,4731359,4732799,4738379,4741163,4744187,4746707,4750739,4752595,4758187,4760983,4764703,4766623,4772223,4774087,4779691,4782491,4785051,4787691,4792491,4794219,4799731,4801971,4805715,4808307,4813683,4815267,4819763,4822323,4826067,4828883,4834519,4835991,4840311,4842935,4846695,4849511,4853991,4855863,4860983,4863383,4866903,4869159,4874487,4876343,4882007,4884599,4887191,4890023,4895695,4897375,4902687,4904927,4908711,4911063,4916747,4918619,4923163,4926007,4929463,4932279,4936599,4938039,4943739,4946379,4950171,4953023,4957583,4959119,4964831,4967687,4971495,4973415,4979135,4981007,4985903,4988751,4991791,4994655,5000175,5002079,5007479,5009399,5012759,5015623,5020615,5022527,5026927,5029799,5033063,5035939,5041695,5043231,5048775,5051375,5055095,5057543,5062151,5063879,5069651,5072387,5076203,5078379,5083251,5085171,5090411,5093303,5096375,5099255,5105047,5106631,5111959,5114199,5118063,5120963,5126767,5128527,5132463,5135367,5138823,5141727,5147543,5149079,5154679,5156983,5160863,5163623,5167783,5169727,5175559,5178475,5181787,5184091,5189635,5191579,5197195,5199883,5202763,5204923,5210775,5212695,5218295,5220631,5224535,5227463,5232479,5234423,5239111,5242039,5245559,5248247,5254123,5255467,5260971,5263911,5267799,5270615,5274935,5276895,5281935,5284575,5288503,5290823,5296247,5298167,5304071,5306591,5309727,5312679,5318591,5320383,5325743,5328047,5331359,5334319,5340243,5341971,5346707,5349671,5353367,5355863,5361799,5363239,5369179,5372147,5376107,5379079,5382919,5384839,5390311,5393287,5397247,5399615,5405015,5406695,5412311,5415287,5418455,5421439,5427151,5429119,5434159,5436271,5440255,5442815,5448575,5450567,5455351,5457895,5461783,5464779,5470775,5472375,5478375,5481183,5484063,5487063,5491863,5493855,5499615,5502559,5506271,5508287,5514307,5516307,5522027,5524747,5527915,5530603,5535763,5537771,5543807,5546207,5549951,5552971,5559015,5560743,5565143,5567959,5571991,5575015,5580583,5582183,5587367,5590391,5594423,5597303,5602151,5603911,5609983,5612503,5616551,5618855,5624935,5626807,5632503,5635543,5638231,5641275,5646795,5648811,5654907,5657307,5661339,5663931,5669811,5671843,5676259,5679299,5683371,5686131,5690883,5692419,5698539,5701599,5705679,5708735,5713631,5715359,5721491,5724275,5727875,5730323,5736227,5738275,5743531,5746443,5749643,5752715,5758475,5760419,5766575,5768495,5772239,5775143,5781307,5783355,5788283,5791367,5794895,5797967,5804143,5805775,5811375,5814463,5818583,5820887,5825831,5827847,5833679,5836775,5840903,5843303,5848607,5850447,5856383,5859455,5862623,5865727,5871439,5873167,5879383,5881863,5885703,5888807,5894447,5896511};
	fin>>n;
	fout<<v[n-1];
	return 0;
}