#!/usr/bin/ruby
require 'prime'
require 'enumerable/lazy' if RUBY_VERSION<'2.0'
T=[21, 63, 291, 502, 2518, 2817, 2991, 4435, 5229, 5367, 5637, 6102, 6174, 6543, 6822, 7236, 7422, 8022, 8541, 8982, 17631, 18231, 18261, 20301, 20518, 20617, 21058, 22471, 22851, 25196, 25918, 27615, 29817, 34816, 35683, 43218, 44305, 45126, 45421, 46818, 49435, 50824, 51363, 51606, 52164, 53967, 54693, 56937, 59002, 59184, 60903, 62118, 63072, 65163, 67045, 67335, 68202, 69271, 71280, 73926, 74259, 74922, 75841, 78120, 78210, 82026, 84283, 85041, 86965, 87109, 89268, 89982, 90282, 94206, 94813, 95217, 98802, 114109, 116503, 119221, 140083, 152301, 157021, 160731, 162619, 166017, 167569, 175821, 176481, 176569, 176931, 179631, 180261, 181465, 182401, 186021, 191607, 192087, 193167, 194181, 199627, 200516, 201123, 201679, 205126, 205916, 208413, 210526, 211065, 212101, 215708, 217508, 224269, 228051, 243007, 245012, 248104, 250126, 250196, 250412, 251926, 251984, 256401, 256761, 257168, 259018, 259136, 259918, 261259, 275103, 277621, 281517, 281805, 281997, 284029, 284301, 285109, 289071, 293001, 301044, 302181, 308124, 310446, 310635, 312658, 320643, 321702, 326516, 326518, 340285, 344169, 348219, 352221, 371244, 371682, 371922, 384109, 384210, 388140, 400399, 400832, 400993, 401184, 404136, 409687, 410124, 410252, 410322, 410328, 410490, 410940, 411726, 412380, 413172, 415638, 417834, 418194, 421052, 428814, 429192, 430218, 431485, 431586, 432405, 434916, 440413, 441670, 441768, 442881, 444018, 449467, 449712, 451302, 452203, 456903, 458712, 461754, 461780, 462285, 462609, 474883, 480231, 480249, 481230, 483605, 490110, 496208, 498208, 500218, 500824, 501642, 502126, 502198, 504601, 504603, 510948, 512636, 514323, 517023, 517722, 525121, 526312, 529443, 534621, 534663, 535761, 538641, 539697, 539967, 544435, 563814, 564102, 567873, 568377, 569397, 571443, 571986, 573012, 574803, 579067, 582109, 584379, 590623, 598914, 599002, 599902, 600102, 600639, 601320, 601983, 602046, 602088, 602910, 603369, 608922, 609714, 610896, 612846, 614376, 615409, 616410, 618150, 618786, 619740, 620235, 620892, 622935, 624903, 625041, 625316, 628902, 629064, 629406, 631032, 632516, 632518, 640170, 641340, 645027, 646071, 650343, 651798, 652318, 653043, 653902, 654231, 657205, 659943, 661579, 674253, 674521, 681120, 681993, 689922, 690816, 693072, 700362, 704232, 706449, 708865, 712800, 720783, 724371, 725238, 725632, 726033, 732031, 734101, 734607, 736297, 736365, 736452, 740421, 742488, 742689, 746539, 747621, 747810, 749682, 749922, 756702, 761502, 763902, 764952, 765234, 768420, 778669, 779281, 780109, 781200, 782100, 782406, 783169, 783522, 802476, 806487, 806511, 812348, 813204, 818053, 820248, 820644, 820674, 821537, 821880, 823452, 825003, 830722, 833782, 840528, 840861, 842104, 842389, 843642, 847692, 848043, 848833, 852091, 857244, 857628, 858276, 865479, 865782, 866527, 869751, 869965, 871290, 872304, 874782, 880567, 892581, 895722, 895761, 896022, 899424, 899982, 904032, 906543, 920262, 924075, 924930, 928638, 932085, 933020, 940212, 940417, 942186, 952230, 957248, 957312, 959607, 964395, 966370, 966753, 972678, 974667, 976384, 976482, 982566, 984370, 989802, 992416, 1014109, 1014901, 1021057, 1026349, 1069261, 1144501, 1148803, 1210669, 1256861, 1281307, 1288663, 1358053, 1362157, 1368403, 1396537, 1399291, 1460203, 1502031, 1504051, 1514419, 1518021, 1520391, 1523091, 1524031, 1527469, 1529301, 1545109, 1576969, 1600281, 1600413, 1600713, 1607481, 1607817, 1688037, 1690641, 1700691, 1704069, 1724319, 1732651, 1736901, 1769913, 1780617, 1781697, 1782513, 1785213, 1786401, 1796841, 1796913, 1796931, 1799631, 1800261, 1802061, 1802961, 1803769, 1822101, 1844229, 1869109, 1876867, 1878523, 1884067, 1890567, 1906137, 1912005, 1914721, 1921741, 1924891, 1928617, 1941057, 1946127, 1956103, 1961485, 1962405, 1970089, 1972431, 1980547, 1981413, 1990521, 2001465, 2005196, 2005912, 2006737, 2010058, 2010105, 2010452, 2012391, 2012506, 2013469, 2014785, 2015708, 2015811, 2017508, 2024163, 2026195, 2029131, 2032581, 2038165, 2042503, 2044501, 2048163, 2050018, 2050198, 2051992, 2051996, 2052531, 2059126, 2059192, 2059912, 2063613, 2084139, 2087341, 2093211, 2094901, 2101065, 2101701, 2103039, 2103459, 2103819, 2104089, 2104947, 2105996, 2106429, 2108584, 2109543, 2109861, 2110905, 2120139, 2120175, 2120506, 2127003, 2134881, 2140269, 2149443, 2149713, 2150647, 2157088, 2157363, 2160195, 2167443, 2170503, 2179508, 2180492, 2181406, 2184904, 2185641, 2195708, 2202417, 2203551, 2209507, 2221873, 2239261, 2243841, 2264157, 2267139, 2270163, 2284657, 2317419, 2320369, 2322781, 2331645, 2340853, 2341501, 2351295, 2356729, 2367351, 2367501, 2381085, 2382351, 2388591, 2406531, 2408104, 2410052, 2410528, 2418057, 2419072, 2427615, 2435101, 2442051, 2459012, 2460531, 2461509, 2463561, 2466417, 2471607, 2500018, 2500198, 2500412, 2501264, 2507517, 2514213, 2515167, 2519206, 2520771, 2523769, 2526351, 2541861, 2560489, 2564001, 2580397, 2588083, 2590423, 2591206, 2591872, 2591936, 2591984, 2599196, 2603689, 2604681, 2607183, 2608173, 2610855, 2612059, 2614941, 2616915, 2618109, 2640717, 2647107, 2648061, 2649211, 2650309, 2651326, 2653912, 2659138, 2668957, 2678517, 2678721, 2698461, 2700441, 2701509, 2710627, 2710821, 2715380, 2728911, 2740162, 2741403, 2743011, 2750319, 2769561, 2781657, 2786983, 2795301, 2810673, 2812635, 2813103, 2815491, 2817255, 2819997, 2854179, 2854851, 2858083, 2868469, 2869791, 2871044, 2881210, 2891061, 2891073, 2903263, 2905821, 2909751, 2910483, 2919339, 2932495, 2934651, 2942271, 2947167, 2947551, 2950137, 2957281, 2957841, 2961045, 2962413, 2964147, 2967381, 2978901, 2981907, 2981997, 2993245, 2998917, 2999481, 3007122, 3009417, 3010125, 3014685, 3026781, 3031092, 3034017, 3041712, 3044169, 3061206, 3076152, 3082003, 3086253, 3093129, 3100836, 3104082, 3104784, 3106458, 3107592, 3120006, 3122679, 3124652, 3130657, 3137265, 3140025, 3144603, 3146083, 3154309, 3158649, 3162501, 3167054, 3193207, 3194809, 3201849, 3202155, 3210280, 3216051, 3247891, 3265018, 3265198, 3280507, 3284019, 3287923, 3296871, 3298093, 3299211, 3316005, 3336199, 3381020, 3385069, 3390471, 3403116, 3405373, 3407691, 3422427, 3428283, 3460309, 3478120, 3480615, 3516874, 3518341, 3520087, 3521718, 3522291, 3560289, 3571268, 3572241, 3582907, 3602529, 3603140, 3624561, 3629223, 3652011, 3654439, 3656347, 3687514, 3689215, 3689251, 3692005, 3692512, 3703669, 3712446, 3715268, 3716214, 3719244, 3719922, 3726249, 3772116, 3817224, 3820183, 3824712, 3824791, 3840921, 3841020, 3842100, 3844049, 3846201, 3849109, 3851251, 3856219, 3881400, 3898140, 3904763, 3912658, 3914802, 3915261, 3921402, 3926518, 3928014, 3940639, 3941082, 3952843, 3991422, 3993012, 4001670, 4002912, 4006287, 4012686, 4013208, 4018812, 4018995, 4020610, 4025012, 4029318, 4031124, 4034172, 4034178, 4035132, 4036923, 4038192, 4038235, 4041525, 4052610, 4052661, 4062517, 4076190, 4081950, 4082047, 4084182, 4084369, 4088347, 4101804, 4102009, 4102052, 4104900, 4106124, 4109400, 4109850, 4117632, 4123800, 4125618, 4133106, 4135788, 4139172, 4144680, 4148640, 4153026, 4154490, 4157928, 4168550, 4170690, 4171734, 4179627, 4180980, 4183290, 4185792, 4187829, 4190278, 4192830, 4198273, 4201038, 4201308, 4206114, 4210099, 4210344, 4213962, 4215906, 4216140, 4217085, 4226877, 4227019, 4228515, 4232491, 4233618, 4235679, 4238251, 4246729, 4248027, 4256979, 4259012, 4259016, 4261149, 4265132, 4268214, 4271832, 4274289, 4278801, 4278823, 4280104, 4284441, 4285818, 4286797, 4290192, 4292865, 4304172, 4306104, 4310064, 4312652, 4314985, 4317696, 4317804, 4317942, 4318002, 4319586, 4319946, 4320655, 4321404, 4322178, 4327164, 4341726, 4349916, 4361958, 4362714, 4404186, 4408104, 4410066, 4410162, 4416249, 4416700, 4417326, 4420239, 4428639, 4432509, 4435621, 4441356, 4441608, 4448214, 4452816, 4463881, 4468813, 4480325, 4482169, 4482393, 4493617, 4500212, 4508703, 4509180, 4510332, 4519638, 4522306, 4531986, 4540176, 4541301, 4557067, 4562431, 4573122, 4589703, 4591206, 4591368, 4600951, 4609710, 4617204, 4617800, 4622445, 4623120, 4623603, 4631058, 4642063, 4659618, 4661598, 4671342, 4673916, 4680027, 4680423, 4681638, 4690188, 4690432, 4695192, 4696009, 4700635, 4703196, 4704102, 4709823, 4716423, 4716432, 4734801, 4750164, 4753512, 4756014, 4763151, 4766767, 4768173, 4776469, 4780152, 4780232, 4781823, 4781943, 4783023, 4791384, 4792170, 4808110, 4809010, 4812300, 4813020, 4813056, 4814305, 4815639, 4820104, 4827255, 4827841, 4829163, 4829301, 4834017, 4836985, 4839109, 4839210, 4839502, 4852035, 4853142, 4861539, 4862106, 4871556, 4873158, 4880190, 4880610, 4881843, 4884381, 4886107, 4894315, 4901100, 4910682, 4919562, 4927167, 4932117, 4962156, 4975104, 4994305, 5000218, 5000824, 5002198, 5004212, 5004225, 5010633, 5012025, 5012026, 5014896, 5016276, 5019210, 5019226, 5020196, 5020198, 5020412, 5020605, 5021264, 5021992, 5023647, 5030259, 5032437, 5032618, 5034063, 5038923, 5041609, 5042106, 5043810, 5050429, 5060130, 5062138, 5063218, 5080024, 5082363, 5082523, 5083416, 5102809, 5103468, 5104428, 5104512, 5108964, 5117643, 5118523, 5120636, 5121360, 5123266, 5126398, 5126976, 5133921, 5136021, 5143170, 5152230, 5154084, 5162076, 5165521, 5177922, 5182776, 5192632, 5193072, 5196726, 5199226, 5202705, 5203143, 5203431, 5209425, 5210026, 5210206, 5210638, 5211864, 5219026, 5221906, 5230618, 5248195, 5251674, 5254657, 5257818, 5260312, 5261130, 5263018, 5266005, 5267829, 5271732, 5274318, 5276178, 5296113, 5300602, 5306218, 5308401, 5311602, 5314734, 5323419, 5339203, 5340663, 5341923, 5354043, 5358861, 5364093, 5365287, 5369997, 5371092, 5374269, 5380657, 5384469, 5389413, 5390062, 5390523, 5394621, 5394663, 5396841, 5396997, 5399062, 5403618, 5403861, 5406231, 5407233, 5419231, 5428966, 5429023, 5433363, 5433867, 5444935, 5451726, 5456218, 5458194, 5461230, 5462931, 5463261, 5470146, 5470832, 5491710, 5498683, 5503923, 5504047, 5512140, 5513422, 5514726, 5518086, 5521230, 5524009, 5525431, 5528637, 5536287, 5552467, 5563143, 5567184, 5576479, 5581206, 5582637, 5592751, 5597269, 5598403, 5600718, 5604831, 5607018, 5610462, 5617782, 5621890, 5629473, 5632110, 5633307, 5634483, 5637018, 5640217, 5641747, 5646337, 5652837, 5656507, 5657733, 5678973, 5687439, 5689818, 5696712, 5697108, 5700318, 5703168, 5719086, 5721480, 5725818, 5731446, 5736669, 5760367, 5761530, 5762420, 5763150, 5782240, 5786883, 5786973, 5787063, 5790312, 5796547, 5809164, 5813316, 5834289, 5834529, 5834610, 5840361, 5843259, 5845003, 5845170, 5847003, 5861032, 5861280, 5862049, 5863833, 5881716, 5886043, 5886817, 5889018, 5890126, 5891166, 5892231, 5893164, 5896134, 5896233, 5900002, 5902126, 5903463, 5904018, 5912026, 5913624, 5917722, 5918670, 5919226, 5922106, 5922837, 5936409, 5939697, 5942010, 5946231, 5949483, 5966307, 5967238, 5967421, 5967612, 5967873, 5969937, 5976144, 5978041, 5978673, 5984379, 5987016, 5988120, 5990002, 5993062, 5993697, 5999024, 5999902, 6000543, 6001230, 6002046, 6006039, 6006150, 6008112, 6010452, 6012030, 6013200, 6017814, 6017841, 6018163, 6020082, 6021135, 6023979, 6025003, 6025371, 6026895, 6028575, 6029064, 6029100, 6038169, 6039180, 6041880, 6048513, 6049188, 6051236, 6051238, 6052318, 6053043, 6053902, 6054231, 6054963, 6059943, 6066357, 6073902, 6077331, 6082965, 6083535, 6090018, 6090381, 6092841, 6093477, 6105138, 6105238, 6106194, 6107013, 6107043, 6107421, 6107463, 6108523, 6123690, 6123960, 6124304, 6128340, 6128580, 6130602, 6132150, 6134220, 6134850, 6135840, 6135912, 6138060, 6139503, 6140898, 6152490, 6164100, 6164730, 6168372, 6173037, 6173982, 6175026, 6178452, 6179841, 6180174, 6180642, 6181500, 6184231, 6197400, 6201672, 6207147, 6208164, 6209568, 6210538, 6210702, 6213789, 6217460, 6219783, 6227251, 6228511, 6228702, 6235803, 6239451, 6241071, 6244419, 6245391, 6246180, 6248041, 6250932, 6251940, 6253018, 6257916, 6261024, 6263197, 6267402, 6281574, 6283041, 6289002, 6290586, 6292008, 6294132, 6298902, 6300327, 6301032, 6302052, 6303150, 6305103, 6305218, 6309126, 6321855, 6325192, 6325196, 6325912, 6325916, 6331050, 6337107, 6349032, 6363855, 6380154, 6381522, 6384607, 6388335, 6391008, 6391902, 6395403, 6398145, 6400393, 6401700, 6402303, 6403683, 6406821, 6409143, 6413400, 6420679, 6429132, 6429180, 6438621, 6444219, 6450120, 6450523, 6451380, 6453260, 6460710, 6461793, 6462171, 6468273, 6480162, 6482106, 6482815, 6484507, 6487110, 6501238, 6502138, 6503218, 6512058, 6512392, 6517098, 6519236, 6520140, 6521038, 6523184, 6530218, 6530824, 6534063, 6539024, 6542391, 6548937, 6564309, 6574923, 6580341, 6581439, 6590043, 6590343, 6592312, 6593043, 6599302, 6613245, 6620975, 6629983, 6630471, 6636841, 6640170, 6640351, 6641847, 6643917, 6644190, 6652710, 6690301, 6693015, 6706092, 6706935, 6711894, 6713802, 6721740, 6722046, 6722082, 6729156, 6730942, 6733083, 6740325, 6740451, 6742224, 6744320, 6749683, 6776343, 6805413, 6808219, 6811200, 6812064, 6823173, 6827052, 6827373, 6827461, 6835401, 6838641, 6840723, 6848010, 6852204, 6854355, 6854922, 6893397, 6899013, 6907021, 6916212, 6916401, 6924021, 6928491, 6929118, 6935229, 6956733, 6964713, 6978150, 6980160, 6980209, 6982362, 6984673, 7018650, 7020324, 7021362, 7021836, 7026037, 7026234, 7032132, 7036245, 7041258, 7042002, 7042032, 7042344, 7042836, 7043922, 7046469, 7053921, 7060635, 7061427, 7065979, 7072218, 7083441, 7086180, 7096473, 7120260, 7123456, 7124526, 7128000, 7128670, 7132248, 7132572, 7135628, 7142058, 7142536, 7142697, 7148005, 7151040, 7152543, 7163079, 7164630, 7167483, 7181820, 7183467, 7191060, 7194267, 7198632, 7202538, 7206280, 7206505, 7206849, 7224372, 7235910, 7236907, 7239571, 7241328, 7243086, 7245396, 7250832, 7251048, 7251402, 7253802, 7254693, 7256403, 7260939, 7270434, 7276201, 7281270, 7284159, 7285410, 7298241, 7304805, 7305264, 7310182, 7312309, 7320159, 7324002, 7324164, 7328352, 7332795, 7340416, 7341426, 7342635, 7354122, 7357291, 7361640, 7366905, 7380349, 7384905, 7390422, 7401489, 7402506, 7407151, 7414362, 7422678, 7424331, 7424892, 7425117, 7426390, 7428618, 7430589, 7432428, 7435026, 7441209, 7449027, 7450243, 7456347, 7457382, 7462584, 7463824, 7464042, 7464582, 7466355, 7478100, 7480843, 7481290, 7485642, 7486452, 7492392, 7492806, 7498629, 7499682, 7507321, 7508491, 7521042, 7522038, 7522146, 7523658, 7526028, 7526208, 7529208, 7536282, 7541262, 7542260, 7554402, 7556301, 7581420, 7600521, 7600563, 7604259, 7610526, 7614810, 7617042, 7624206, 7631220, 7635501, 7652052, 7663057, 7664526, 7665883, 7665937, 7680643, 7682040, 7683039, 7683514, 7684200, 7684287, 7692080, 7712082, 7715244, 7721352, 7724619, 7725024, 7732152, 7761429, 7773264, 7780363, 7796280, 7802406, 7812000, 7819560, 7820145, 7821000, 7821403, 7836192, 7841203, 7842105, 7860582, 7865019, 7873695, 7895292, 7902709, 7902889, 7923571, 7924057, 7962642, 7982214, 8005824, 8009352, 8013222, 8021430, 8027856, 8028534, 8032236, 8036424, 8040483, 8043822, 8043865, 8044587, 8046027, 8049609, 8050024, 8056371, 8062248, 8064273, 8067357, 8073439, 8080632, 8085067, 8087469, 8113602, 8121960, 8123821, 8124006, 8124811, 8125740, 8126467, 8137224, 8140230, 8142345, 8149590, 8152092, 8152776, 8159643, 8161207, 8162568, 8164539, 8179261, 8180472, 8188290, 8204104, 8204586, 8205732, 8207396, 8210880, 8211051, 8213040, 8217324, 8218800, 8230059, 8243640, 8249796, 8252341, 8257302, 8258307, 8259606, 8270082, 8270539, 8271576, 8275122, 8276958, 8280673, 8283795, 8285910, 8287335, 8293656, 8296207, 8304975, 8312499, 8315674, 8316907, 8319823, 8320305, 8326170, 8333410, 8351674, 8352549, 8352567, 8355429, 8356714, 8357265, 8357821, 8358246, 8366965, 8367471, 8371969, 8374206, 8375026, 8382240, 8392662, 8395272, 8402893, 8402904, 8420688, 8424066, 8425092, 8427924, 8428921, 8434051, 8434755, 8437062, 8450472, 8456019, 8461572, 8463152, 8467236, 8467851, 8472024, 8480025, 8480862, 8481507, 8488563, 8502633, 8524818, 8525034, 8525367, 8536179, 8536302, 8536428, 8542701, 8547093, 8548032, 8549679, 8551269, 8551602, 8554752, 8560479, 8562924, 8562942, 8563248, 8565822, 8570286, 8572446, 8578287, 8579401, 8588043, 8598762, 8605795, 8609274, 8610072, 8610528, 8612022, 8614305, 8617527, 8624502, 8628507, 8628534, 8635257, 8637154, 8642106, 8642808, 8642916, 8649405, 8649459, 8652537, 8654049, 8654979, 8658945, 8662957, 8663220, 8670216, 8670222, 8670573, 8682397, 8682507, 8687928, 8690652, 8691480, 8692857, 8695602, 8695782, 8696005, 8698410, 8699605, 8699751, 8700462, 8700989, 8705202, 8705509, 8705673, 8712900, 8721130, 8721421, 8724096, 8725428, 8725806, 8727181, 8735022, 8752092, 8757843, 8769067, 8807571, 8814294, 8820657, 8825463, 8844057, 8845953, 8853129, 8854689, 8860777, 8896428, 8902251, 8905257, 8910657, 8925546, 8932410, 8936424, 8942064, 8942406, 8943642, 8954268, 8957628, 8957682, 8957961, 8960274, 8967051, 8969112, 8976942, 8990701, 8995722, 8995761, 8996256, 9005463, 9018459, 9018889, 9022086, 9028458, 9029628, 9035622, 9036072, 9037692, 9039726, 9042615, 9043850, 9045681, 9050682, 9072408, 9080017, 9080809, 9085437, 9085524, 9086832, 9087435, 9126810, 9142284, 9145062, 9148032, 9148093, 9167403, 9172461, 9179251, 9184665, 9202050, 9205374, 9206838, 9214020, 9216084, 9224550, 9242955, 9249300, 9254601, 9260331, 9265489, 9271545, 9274062, 9281466, 9281637, 9282330, 9287511, 9294048, 9330200, 9333280, 9350802, 9360642, 9376567, 9390762, 9401220, 9401607, 9406429, 9408204, 9415560, 9420732, 9421608, 9423246, 9436705, 9440262, 9475443, 9482220, 9503647, 9506025, 9520056, 9522300, 9523860, 9524367, 9536767, 9537721, 9538603, 9552807, 9581409, 9587316, 9590841, 9597312, 9601344, 9602550, 9605250, 9605763, 9606465, 9607134, 9608481, 9610128, 9611346, 9612702, 9618357, 9620675, 9620883, 9624573, 9635085, 9640208, 9644907, 9650781, 9652968, 9653649, 9656253, 9663700, 9686293, 9686403, 9687607, 9690649, 9693126, 9698472, 9701235, 9701325, 9702396, 9706467, 9720367, 9748269, 9749667, 9776527, 9780416, 9783650, 9784152, 9784629, 9792678, 9800989, 9804645, 9807425, 9810889, 9822078, 9824075, 9824104, 9834280, 9842104, 9843700, 9848203, 9852001, 9853020, 9860202, 9862155, 9863127, 9864651, 9866052, 9880189, 9886509, 9899802, 9923393, 9933012, 9944230, 9960021, 9966730, 9970632, 9983167]

class Integer
	def totient
		self.prime_division.reduce(1){|s,e|s*(e[0]-1)*e[0]**(e[1]-1)}
	end
	def totient2
		r=self.totient
		a=self.to_s.bytes.sort
		b=r.to_s.bytes.sort
		return a==b
	end
end
#T=(2...10000000).select(&:totient2)
h={};T.each{|e|h[e]=1}
p (2...gets.to_i).select{|e|h.include?(e)}.min_by{|n|n.to_f/n.totient}
__END__
10000000