#include <cstdio>
//#include "out.txt"

long long H1[] = {
	1LL,
	2LL,
	4LL,
	6LL,
	16LL,
	12LL,
	64LL,
	24LL,
	36LL,
	48LL,
	1024LL,
	60LL,
	4096LL,
	192LL,
	144LL,
	120LL,
	180LL,
	240LL,
	576LL,
	3072LL,
	360LL,
	1296LL,
	12288LL,
	900LL,
	960LL,
	720LL,
	840LL,
	9216LL,
	5184LL,
	1260LL,
	36864LL,
	1680LL,
	2880LL,
	15360LL,
	3600LL,
	2520LL,
	46656LL,
	6480LL,
	61440LL,
	6300LL,
	82944LL,
	6720LL,
	5040LL,
	14400LL,
	7560LL,
	331776LL,
	46080LL,
	25920LL,
	10080LL,
	32400LL,
	746496LL,
	184320LL,
	15120LL,
	44100LL,
	20160LL,
	107520LL,
	25200LL,
	2985984LL,
	27720LL,
	233280LL,
	230400LL,
	45360LL,
	430080LL,
	129600LL,
	50400LL,
	414720LL,
	60480LL,
	921600LL,
	55440LL,
	60466176LL,
	810000LL,
	100800LL,
	83160LL,
	1658880LL,
	322560LL,
	176400LL,
	181440LL,
	241864704LL,
	110880LL,
	1166400LL,
	226800LL,
	3732480LL,
	1290240LL,
	166320LL,
	352800LL,
	2073600LL,
	221760LL,
	2176782336LL,
	3240000LL,
	967680LL,
	277200LL,
	14929920LL,
	705600LL,
	332640LL,
	8294400LL,
	1632960LL,
	1612800LL,
	498960LL,
	3870720LL,
	907200LL,
	554400LL,
	2903040LL,
	665280LL,
	1587600LL,
	18662400LL,
	6451200LL,
	720720LL,
	302330880LL,
	2822400LL,
	29160000LL,
	5670000LL,
	1108800LL,
	1081080LL,
	11612160LL,
	3548160LL,
	1940400LL,
	74649600LL,
	51840000LL,
	1995840LL,
	1209323520LL,
	1441440LL,
	8164800LL,
	11289600LL,
	2494800LL,
	26127360LL,
	14192640LL,
	6350400LL,
	2162160LL,
	3880800LL,
	207360000LL,
	14515200LL,
	2882880LL,
	10883911680LL,
	729000000LL,
	22680000LL,
	45158400LL,
	10644480LL,
	3603600LL,
	1511654400LL,
	104509440LL,
	39690000LL,
	7761600LL,
	4324320LL,
	466560000LL,
	58060800LL,
	17962560LL,
	17740800LL,
	6486480LL,
	21344400LL,
	42577920LL,
	9979200LL,
	6046617600LL,
	7207200LL,
	31933440LL,
	57153600LL,
	8648640LL,
	17463600LL,
	1866240000LL,
	130636800LL,
	70963200LL,
	10810800LL,
	2116316160LL,
	31046400LL,
	204120000LL,
	101606400LL,
	62370000LL,
	14414400LL,
	54419558400LL,
	17297280LL,
	127733760LL,
	158760000LL,
	46126080LL,
	11664000000LL,
	25225200LL,
	522547200LL,
	362880000LL,
	25945920LL,
	85377600LL,
	8465264640LL,
	21621600LL,
	406425600LL,
	89812800LL,
	124185600LL,
	32432400LL,
	37791360000LL,
	287400960LL,
	184504320LL,
	1944810000LL,
	69854400LL,
	46656000000LL,
	36756720LL,
	50450400LL,
	1451520000LL,
	159667200LL,
	43243200LL,
	192099600LL,
	76187381760LL,
	5103000000LL,
	914457600LL,
	249480000LL,
	496742400LL,
	138378240LL,
	151165440000LL,
	61261200LL,
	10581580800LL,
	1149603840LL,
	341510400LL,
	1428840000LL,
	436590000LL,
	100900800LL,
	73513440LL,
	3265920000LL,
	638668800LL,
	233513280LL,
	230630400LL,
	110270160LL,
	277477200LL,
	3657830400LL,
	2540160000LL,
	553512960LL,
	129729600LL,
	1360488960000LL,
	944784000000LL,
	42326323200LL,
	122522400LL,
	7779240000LL,
	415134720LL,
	628689600LL,
	1366041600LL,
	147026880LL,
	227026800LL,
	13063680000LL,
	1437004800LL,
	922521600LL,
	768398400LL,
	183783600LL,
	23279477760LL,
	403603200LL,
	10160640000LL,
	2245320000LL,
	1117670400LL,
	810810000LL,
	3779136000000LL,
	245044800LL,
	380936908800LL,
	294053760LL,
	35721000000LL,
	1660538880LL,
	1746360000LL,
	5464166400LL,
	691891200LL,
	81648000000LL,
	428828400LL,
	74071065600LL,
	5748019200LL,
	3991680000LL,
	441080640LL,
	4802490000LL,
	1109908800LL,
	93117911040LL,
	367567200LL,
	22861440000LL,
	4470681600LL,
	1167566400LL,
	34012224000000LL,
	1614412800LL,
	551350800LL,
	264539520000LL,
	3073593600LL,
	70013160000LL,
	3736212480LL,
	2767564800LL,
	21392910000LL,
	908107200LL,
	326592000000LL,
	698377680LL,
	296284262400LL,
	857656800LL,
	15966720000LL,
	2075673600LL,
	6915585600LL,
	590490000000000LL,
	735134400LL,
	2497294800LL,
	838061199360LL,
	91445760000LL,
	56133000000LL,
	124467840000LL,
	10059033600LL,
	3243240000LL,
	6457651200LL,
	2352430080LL,
	1058158080000LL,
	1102701600LL,
	116397388800LL,
	14944849920LL,
	4439635200LL,
	15717240000LL,
	12294374400LL,
	5675670000LL,
	1715313600LL,
	2666558361600LL,
	1396755360LL,
	35925120000LL,
	8302694400LL,
	3969725760LL,
	2361960000000000LL,
	19209960000LL,
	3920716800LL,
	2095133040LL,
	571536000000LL,
	3632428800LL,
	497871360000LL,
	40236134400LL,
	27941760000LL,
	9409720320LL,
	2205403200LL,
	9523422720000LL,
	6613488000000LL,
	14428814400LL,
	1750329000000LL,
	465589555200LL,
	2327925600LL,
	85571640000LL,
	49177497600LL,
	7057290240LL,
	8172964800LL,
	17758540800LL,
	2793510720LL,
	3859455600LL,
	1851776640000LL,
	143700480000LL,
	18681062400LL,
	21257640000000000LL,
	15682867200LL,
	235322010000LL,
	9989179200LL,
	2286144000000LL,
	3491888400LL,
	1120210560000LL,
	302633210880LL,
	6861254400LL,
	111767040000LL,
	29189160000LL,
	14529715200LL,
	13783770000LL,
	26453952000000LL,
	4655851200LL,
	32464832400LL,
	4190305996800LL,
	5587021440LL,
	392931000000LL,
	110649369600LL,
	28229160960LL,
	22702680000LL,
	71034163200LL,
	11762150400LL,
	7407106560000LL,
	898128000000LL,
	7718911200LL,
	814781721600LL,
	74724249600LL,
	57715257600LL,
	531441000000000000LL,
	51891840000LL,
	172889640000LL,
	8380532160LL,
	62432370000LL,
	18868449600LL,
	4480842240000LL,
	1210532843520LL,
	6983776800LL,
	251475840000LL,
	58118860800LL,
	19848628800LL,
	238085568000000LL,
	27445017600LL,
	10475665200LL,
	85766121000000LL,
	2909934720000LL,
	39956716800LL,
	770144760000LL,
	442597478400LL,
	63515612160LL,
	307359360000LL,
	47048601600LL,
	278107830000LL,
	15437822400LL,
	66663959040000LL,
	46294416000000LL,
	3592512000000LL,
	16062686640LL,
	3259126886400LL,
	16295479200LL,
	207567360000LL,
	941288040000LL,
	35286451200LL,
	89902612800LL,
	4133430000000000LL,
	230861030400LL,
	13967553600LL,
	28005264000000LL,
	42454011600LL,
	10894795591680LL,
	1005903360000LL,
	729729000000LL,
	1369146240000LL,
	130767436800LL,
	55135080000LL,
	109780070400LL,
	44696171520LL,
	129859329600LL,
	11639738880000LL,
	20951330400LL,
	1513166054400LL,
	254062448640LL,
	75473798400LL,
	1229437440000LL,
	204324120000LL,
	159826867200LL,
	96486390000LL,
	185177664000000LL,
	32590958400LL,
	90737055360000LL,
	29332141977600LL,
	27935107200LL,
	467026560000LL,
	4322241000000LL,
	141145804800LL,
	28473963210000LL,
	75424789440LL,
	16533720000000000LL,
	249729480000LL,
	923444121600LL,
	74493619200LL,
	112021056000000LL,
	48188059920LL,
	6286896000000LL,
	61751289600LL,
	5476584960000LL,
	8962598937600LL,
	523069747200LL,
	363242880000LL,
	178784686080LL,
	41902660800LL,
	811620810000LL,
	104757649920000LL,
	72748368000000LL,
	245289844800LL,
	19253619000000LL,
	6052664217600LL,
	48886437600LL,
	2766234240000LL,
	1112431320000LL,
	639307468800LL,
	134088514560LL,
	138940401600LL,
	1666598976000000LL,
	301895193600LL,
	362948221440000LL,
	64250746560LL,
	73329656400LL,
	20369543040000LL,
	1868106240000LL,
	519437318400LL,
	8471592360000LL,
	317578060800LL,
	148803480000000000LL,
	297974476800LL,
	3059186130000LL,
	1372257936000000LL,
	169816046400LL,
	25147584000000LL,
	80313433200LL,
	12322316160000LL,
	35850395750400LL,
	5144764584960LL,
	130363833600LL,
	1452971520000LL,
	496215720000LL,
	247005158400LL,
	1168733966400LL,
	28934010000000000LL,
	261891630000LL,
	290993472000000LL,
	97772875200LL,
	551902150800LL,
	54473977958400LL,
	11064936960000LL,
	128501493120LL,
	5108103000000LL,
	15060608640000LL,
	1438441804800LL,
	536354058240LL,
	385945560000LL,
	1207580774400LL,
	223480857600LL,
	3266533992960000LL,
	2268426384000000LL,
	81478172160000LL,
	11675664000000LL,
	146659312800LL,
	10592162380800LL,
	1270312243200LL,
	981159379200LL,
	113895852840000LL,
	882161280000LL,
	2247565320000LL,
	2077749273600LL,
	5489031744000000LL,
	192752239680LL,
	1061350290000LL,
	358500542400LL,
	49289264640000LL,
	322653561753600LL,
	20579058339840LL,
	160626866400LL,
	3269185920000LL,
	988020633600LL,
	377123947200LL,
	115736040000000000LL,
	3246483240000LL,
	2618941248000000LL,
	521455334400LL,
	240940299600LL,
	943427331000000LL,
	37829151360000LL,
	69155856000000LL,
	679264185600LL,
	60242434560000LL,
	10011881880000LL,
	5753767219200LL,
	1206796631040LL,
	3995671680000LL,
	893923430400LL,
	4727833110000LL,
	9073705536000000LL,
	293318625600LL,
	733303549440000LL,
	509238576000000LL,
	46702656000000LL,
	4169927361600LL,
	385504479360LL,
	211789809000000LL,
	42368649523200LL,
	374796021600LL,
	3528645120000LL,
	12236744520000LL,
	8310997094400LL,
	670442572800LL,
	1528344417600LL,
	45467730000000000LL,
	3924637516800LL,
	321253732800LL,
	308057904000000LL,
	806626220400LL,
	185211525058560LL,
	224064973440000LL,
	13076743680000LL,
	12405393000000LL,
	17798901120000LL,
	2223046425600LL,
	1041624360000000000LL,
	1047566520000LL,
	2085821337600LL,
	39769419690000LL,
	1028011944960LL,
	2207608603200LL,
	151316605440000LL,
	276623424000000LL,
	481880599200LL,
	135545477760000LL,
	25723822924800LL,
	4827186524160LL,
	1434002169600LL,
	15982686720000LL,
	3473510040000LL,
	81663349824000000LL,
	111152892816000000LL,
	2717056742400LL,
	1833241410000LL,
	2036954304000000LL,
	749592043200LL,
	998107608960000LL,
	9382336563600LL,
	381317845708800LL,
	1025062675560000LL,
	642507465600LL,
	7939451520000LL,
	56189133000000LL,
	18699743462400LL,
	2681770291200LL,
	370161521730000LL,
	1734770157120LL,
	181870920000000000LL,
	4245401160000LL,
	15698550067200LL,
	1564366003200LL,
	1232231616000000LL,
	1204701498000LL,
	896259893760000LL,
	81729648000000LL,
	1173274502400LL,
	71195604480000LL,
	116513786188800LL,
	8892185702400LL,
	16679709446400LL,
	6175128960000LL,
	29218349160000LL,
	1417766490000000000LL,
	4112047779840LL,
	963761198400LL,
	13797553770000LL,
	1361849448960000LL,
	945728784000000LL,
	4660507051200LL,
	542181911040000LL,
	250297047000000LL,
	102895291699200LL,
	1822333645440000LL,
	1124388064800LL,
	35961045120000LL,
	18911332440000LL,
	444611571264000000LL,
	10868226969600LL,
	3084035834880LL,
	2639867630400LL,
	18332588736000000LL,
	5736008678400LL,
	3992430435840000LL,
	1606268664000LL,
	1686582097200LL,
	10377700641000000LL,
	264804059520000LL,
	31757806080000LL,
	8830434412800LL,
	110130700680000LL,
	74798973849600LL,
	6033983155200LL,
	51943731840000LL,
	1636838280000000000LL,
	6257464012800LL,
	52006164210000LL,
	15094837296000000LL,
	3226504881600LL,
	8066339043840000LL,
	5601624336000000LL,
	326918592000000LL,
	1927522396800LL,
	160190110080000LL,
	466055144755200LL,
	97750527114240LL,
	2998368172800LL,
	24700515840000LL,
	9428098680000LL,
	159077678760000LL,
	4693098009600LL,
	19868477428800LL,
	318274110000000000LL,
	6023507490000LL,
	3782915136000000LL,
	66718837785600LL,
	2248776129600LL,
	3388636944000000LL,
	10486140865200LL,
	926057625292800LL,
	7289334581760000LL,
	143844180480000LL,
	3212537328000LL,
	86837751000000LL,
	195787912320000LL,
	24453510681600LL,
	12336143339520LL,
	7332965640000LL,
	22944034713600LL,
	5140059724800LL,
	35931873922560000LL,
	24952690224000000LL,
	37529346254400LL,
	25626566889000000LL,
	1059216238080000LL,
	198486288000000LL,
	3373164194400LL,
	180066760473600LL,
	24135932620800LL,
	18642028204800LL,
	1480646086920000LL,
	207774927360000LL,
	16761064320000LL,
	38208610440000LL,
	35321737651200LL,
	60379349184000000LL,
	4818805992000LL,
	20165655510000LL,
	22406497344000000LL,
	8245512475200LL,
	10979183698560000LL,
	640760440320000LL,
	4194496302796800LL,
	391002108456960LL,
	4497552259200LL,
	55576160640000LL,
	730458729000000LL,
	18772392038400LL,
	4812099782490000LL,
	8673850785600LL,
	1273096440000000000LL,
	55190215080000LL,
	34046236224000000LL,
	266875351142400LL,
	11993472691200LL,
	13554547776000000LL,
	6987268688400LL,
	12264555303000000LL,
	16401002808960000LL,
	643095573120000LL,
	899026128000000LL,
	12906019526400LL,
	783151649280000LL,
	170201991960000LL,
	1514679220454400LL,
	97814042726400LL,
	27756322513920LL,
	67926418560000LL,
	20560238899200LL,
	89828829090000LL,
	99810760896000000LL,
	6746328388800LL,
	234558414090000LL,
	9532946142720000LL,
	6620101488000000LL,
	793945152000000LL,
	79228619870400LL,
	9637611984000LL,
	2753267517000000LL,
	720267041894400LL,
	8995104518400LL,
	467493586560000LL,
	67044257280000LL,
	208024656840000LL,
	141286950604800LL,
	15420179174400LL,
	29038543934400LL,
	201658476096000000LL,
	591080490000000000LL,
	74568112819200LL,
	43916734794240000LL,
	9316358251200LL,
	4004752752000000LL,
	18552403069200LL,
	3519018976112640LL,
	2912844654720000LL,
	222304642560000LL,
	150117385017600LL,
	235702467000000LL,
	302581319040000LL,
	1431699108840000LL,
	42237882086400LL,
	24094029960000LL,
	47973890764800LL,
	676080134730000LL,
	25700298624000LL,
	166043210256000000LL,
	41944563460800LL,
	65604011235840000LL,
	2572382292480000LL,
	3596104512000000LL,
	13492656777600LL,
	1762091210880000LL,
	6058716881817600LL,
	488752635571200LL,
	111025290055680LL,
	32982049900800LL,
	271705674240000LL,
	65996690760000LL,
	898296848064000000LL,
	1222681820976000000LL,
	51624078105600LL,
	337764116289600LL,
	42164552430000LL,
	1255701777561000000LL,
	26480405952000000LL,
	20238985166400LL,
	12975398916480000LL,
	178264394708400LL,
	6482403377049600LL,
	13325814782280000LL,
	1869974346240000LL,
	18632716502400LL,
	150849578880000LL,
	955215261000000LL,
	2545242860160000LL,
	317895638860800LL,
	61680716697600LL,
	6292745869410000LL,
	43369253928000LL,
	80662622040000LL,
	298272451276800LL,
	35980418073600LL,
	395250613148160000LL,
	274479592464000000LL,
	16019011008000000LL,
	34936343442000LL,
	11651378618880000LL,
	1389404016000000LL,
	26985313555200LL,
	1210325276160000LL,
	1980734365209600LL,
	168951528345600LL,
	316914479481600LL,
	19248399129960000LL,
	117327450240000LL,
	496711935720000LL,
	102801194496000LL,
	600469540070400LL,
	664172841024000000LL,
	27949074753600LL,
	410025070224000000LL,
	262153521630000LL,
	23151440632320000LL,
	16077389328000000LL,
	107191662177600LL,
	7048364843520000LL,
	54528451936358400LL,
	4255049799000000LL,
	1955010542284800LL,
	23690337390720000LL,
	32607253879200LL,
	611337767040000LL,
	359315316360000LL,
	206496312422400LL,
	77100895872000LL,
	60716955499200LL,
	938233656360000LL,
	238323653568000000LL,
	131928199603200LL,
	51901595665920000LL,
	46581791256000LL,
	48910880818800LL,
	134910108333000000LL,
	4501669011840000LL,
	11687339664000000LL,
	603398315520000LL,
	167778253843200LL,
	10180971440640000LL,
	1872221911560000LL,
	1271582555443200LL,
	138781612569600LL,
	883043441280000LL,
	143921672294400LL,
	988117119990000LL,
	1097918369856000000LL,
	196232884848000000LL,
	74209612276800LL,
	1328481227525760000LL,
	104862407569920000LL,
	72821116368000000LL,
	5557616064000000LL,
	1351056465158400LL,
	55898149507200LL,
	2723231871360000LL,
	35792477721000000LL,
	7922937460838400LL,
	2248262123627520LL,
	80955940665600LL,
	469309800960000LL,
	813244863240810000LL,
	216846269640000LL,
	2704320538920000LL,
	2401878160281600LL,
	107941254220800LL,
	377501071147200LL,
	1640100280896000000LL,
	174681717210000LL,
	64309557312000000LL,
	1267657917926400LL,
	65214507758400LL,
	44052280272000000LL,
	241181239899600LL,
	17595094880563200LL,
	94761349562880000LL,
	37866980511360000LL,
	2445351068160000LL,
	93163582512000LL,
	1649917269000000LL,
	3328394509440000LL,
	464616702950400LL,
	308403583488000LL,
	168658209720000LL,
	527712798412800LL,
	11493362290410000LL,
	149061732019200LL,
	467114360993280000LL,
	324384972912000000LL,
	713057578833600LL,
	333145369557000000LL,
	18006676047360000LL,
	46749358656000000LL,
	3771239472000000LL,
	97821761637600LL,
	22907185741440000LL,
	3421268448998400LL,
	555126450278400LL,
	428766648710400LL,
	25170983477640000LL,
	3532173765120000LL,
	385504479360000LL,
	725963598360000LL,
	671113015372800LL,
	784931539392000000LL,
	139745373768000LL,
	463810076730000LL,
	291284465472000000LL,
	222628836830400LL,
	142729388081280000LL,
	10892927485440000LL,
	3387023499459600LL,
	71306437147545600LL,
	8993048494510080LL,
	173235592169640000LL,
	130429015516800LL,
	1055947052160000LL,
	12417798393000000LL,
	5404225860633600LL,
	431765016883200LL,
	81805696302330000LL,
	251541672782400LL,
	1048614086520000LL,
	578786015808000000LL,
	5070631671705600LL,
	323823762662400LL,
	176209121088000000LL,
	216605329340400LL,
	208497440151000000LL,
	213213036516480000LL,
	151467922045440000LL,
	12218815889280000LL,
	15283444176000000LL,
	296838449107200LL,
	13313578037760000LL,
	3233837847240000LL,
	25749546747724800LL,
	1858466811801600LL,
	6021375110150400LL,
	693908062848000LL,
	1290601952640000LL,
	8444102907240000LL,
	596246928076800LL,
	2066063069070000LL,
	1297539891648000000LL,
	195643523275200LL,
	4456609867710000LL,
	162060084426240000LL,
	112541725296000000LL,
	15084957888000000LL,
	1510004284588800LL,
	91628742965760000LL,
	279490747536000LL,
	46805547789000000LL,
	13685073795993600LL,
	307974386079360000LL,
	260858031033600LL,
	7947390971520000LL,
	1542017917440000LL,
	3952468479960000LL,
	2684452061491200LL,
	447185196057600LL,
	667886510491200LL,
	1715066594841600LL,
	570917552325120000LL,
	288807105787200LL,
	68080796784000000LL,
	538019689006800LL,
	1753831408329000000LL,
	80937436450590720LL,
	49518359130240000LL,
	4223788208640000LL,
	2852230315334400LL,
	5421156741000000LL,
	5749045061760000LL,
	24338884850280000LL,
	21616903442534400LL,
	971471287987200LL,
	15011738501760000LL,
	698726868840000LL,
	1295295050649600LL,
	12845522559870000LL,
	745308660096000LL,
	964724959598400LL,
	852852146065920000LL,
	1363211298408960000LL,
	946674512784000000LL,
	48875263557120000LL,
	61133776704000000LL,
	391287046550400LL,
	29955550584960000LL,
	102998186990899200LL,
	11241310618137600LL,
	2775632251392000LL,
	890515347321600LL,
	5162407810560000LL,
	1517923887480000LL,
	45973449161640000LL,
	1187353796428800LL,
	6417518209502400LL,
	1222772020470000LL,
	450166901184000000LL,
	24085500440601600LL,
	586930569825600LL,
	220581781580160000LL,
	572679643536000000LL,
	4100081078293200LL,
	123165664163942400LL,
	1231897544317440000LL,
	226538851298760000LL,
	31789563886080000LL,
	577614211574400LL,
	3469540314240000LL,
	18149089959000000LL,
	43269128622720000LL,
	6040017138355200LL,
	1788740784230400LL,
	119562171518790000LL,
	1257708363912000LL,
	1855240306920000LL,
	6860266379366400LL,
	1043432124134400LL,
	272323187136000000LL,
	13548093997838400LL,
	1083026646702000LL,
	198073436520960000LL,
	26398676304000000LL,
	782574093100800LL,
	22996180247040000LL,
	37633952938982400LL,
	3885885151948800LL,
	7289033028076800LL,
	327222785209320000LL,
	60046954007040000LL,
	2698531355520000LL,
	9437526778680000LL,
	2981234640384000LL,
	11408921261337600LL,
	866421317361600LL,
	6029530997490000LL,
	439877372014080000LL,
	305470397232000000LL,
	2671546041964800LL,
	1855482045056640000LL,
	119822202339840000LL,
	926983682918092800LL,
	80845946181000000LL,
	44965242472550400LL,
	402735735642240000LL,
	1010824870255200LL,
	11615417573760000LL,
	211102572681000000LL,
	8264252276280000LL,
	4749415185715200LL,
	1390696837139610000LL,
	2235925980288000LL,
	1760791709476800LL,
	17826439470840000LL,
	96342001762406400LL,
	3562061389286400LL,
	882327126320640000LL,
	1444035528936000LL,
	1516237305382800LL,
	85531711224960000LL,
	198684774288000000LL,
	13878161256960000LL,
	3858899838393600LL,
	173076514490880000LL,
	35572216319640000LL,
	437742294711321600LL,
	24160068553420800LL,
	4024666764518400LL,
	16777825384320000LL,
	4173728496537600LL,
	22726693759770000LL,
	2152078756027200LL,
	84675587486490000LL,
	1782660928688640000LL,
	1237958978256000000LL,
	105594705216000000LL,
	25670072838009600LL,
	1732842634723200LL,
	51741405555840000LL,
	608472121257000000LL,
	150535811755929600LL,
	56206553090688000LL,
	2347722279302400LL,
	135105646515840000LL,
	10794125422080000LL,
	6288541819560000LL,
	51382090239480000LL,
	45635685045350400LL,
	3130296372403200LL,
	8682524636385600LL,
	5415133233510000LL,
	1221881588928000000LL,
	29156132112307200LL,
	2021649740510400LL,
	748888764624000000LL,
	6994255957088400LL,
	404687182252953600LL,
	1610942942568960000LL,
	643738668693120000LL,
	46461670295040000LL,
	2888071057872000LL,
	54192375991353600LL,
	37948097187000000LL,
	63239495679360000LL,
	413761042454760000LL,
	10686184167859200LL,
	8943703921152000LL,
	4891088081880000LL,
	14248245557145600LL,
	218373883517790000LL,
	4620913692595200LL,
	16400324313172800LL,
	342126844899840000LL,
	794739097152000000LL,
	86738507856000000LL,
	3032474610765600LL,
	389422157604480000LL,
	1750969178845286400LL,
	78689174326963200LL,
	16098667058073600LL,
	11576699515180800LL,
	478248686075160000LL,
	67111301537280000LL,
	11179629901440000LL,
	16697162762280000LL,
	15435599353574400LL,
	121932845980545600LL,
	4332106586808000LL,
	13450492225170000LL,
	6456236268081600LL,
	206965622223360000LL,
	71305757883360000LL,
	1354822305803366400LL,
	224826212362752000LL,
	540422586063360000LL,
	4043299481020800LL,
	24286782199680000LL,
	235938169467000000LL,
	735575186586240000LL,
	102680291352038400LL,
	12521185489612800LL,
	1554308229744270000LL,
	7797791856254400LL,
	24118123989960000LL,
	116624528449228800LL,
	9390889117209600LL,
	6931370538892800LL,
	281032765453440000LL,
	290385439344000000LL,
	8608315024108800LL,
	252957982717440000LL,
	74378270486520000LL,
	489241388206771200LL,
	42744736671436800LL,
	138491627533459200LL,
	20123333822592000LL,
	29683844910720000LL,
	160437955237560000LL,
	18483654770380800LL,
	59915829003030000LL,
	216769503965414400LL,
	6064949221531200LL,
	102502026957330000LL,
	346954031424000000LL,
	34730098545542400LL,
	1557688630417920000LL,
	8664213173616000LL,
	889305407991000000LL,
	314756697307852800LL,
	8086598962041600LL,
	151000428458880000LL,
	44718519605760000LL,
	90906775039080000LL,
	61742397414297600LL,
	13862741077785600LL,
	19368708804244800LL,
	338702349945960000LL,
	46306798060723200LL,
	10108248702552000LL,
	1293535138896000000LL,
	16678610359210800LL,
	940848823474560000LL,
	97147128798720000LL,
	65601297252691200LL,
	157213545489000000LL,
	132228036420480000LL,
	462438812155320000LL,
	410721165408153600LL,
	28172667351628800LL,
	285223031533440000LL,
	21660532934040000LL,
	37563556468838400LL,
	295447018877010000LL,
	23104568462976000LL,
	27977023828353600LL,
	1124131061813760000LL,
	1161541757376000000LL,
	487731383922182400LL,
	12129898443062400LL,
	569155461114240000LL,
	1956965552827084800LL,
	325998007925990400LL,
	80493335290368000LL,
	25824945072326400LL,
	118735379642880000LL,
	44019792736920000LL,
	873495534071160000LL,
	867078015861657600LL,
	34433260096435200LL,
	147602918818555200LL,
	37905932634570000LL,
	553966510133836800LL,
	18194847664593600LL,
	96472495959840000LL,
	604001713835520000LL,
	20216497405104000LL,
	100616669112960000LL,
	417429069057000000LL,
	822113443831680000LL,
	138920394182169600LL,
	55450964311142400LL,
	38988959281272000LL,
	53801968900680000LL,
	185227192242892800LL,
	32346395848166400LL,
	311606161950283200LL,
	34656852694464000LL,
	607169554992000000LL,
	24259796886124800LL,
	528912145681920000LL,
	865580917596595200LL,
	112690669406515200LL,
	196803891758073600LL,
	1140892126133760000LL,
	78257409310080000LL,
	217063115909640000LL,
	92418273851904000LL,
	262405189010764800LL,
	30324746107656000LL,
	174856398927210000LL,
	77474835216979200LL,
	1354809399783840000LL,
	1859456762163000000LL,
	1303992031703961600LL,
	36389695329187200LL,
	267154604196480000LL,
	239663316012120000LL,
	1950925535688729600LL,
	137733040385740800LL,
	69313705388928000LL,
	54584542993780800LL,
	410008107829320000LL,
	103299780289305600LL,
	53429314570632000LL,
	48519593772249600LL,
	1967229358174080000LL,
	402466676451840000LL,
	111908095313414400LL,
	818160975351720000LL,
	555681576728678400LL,
	124764669700070400LL,
	385889983839360000LL,
	129385583392665600LL,
	659074119033330000LL,
	66714441436843200LL,
	1947538512189270000LL,
	590411675274220800LL,
	60649492215312000LL,
	1190052327784320000LL,
	1629990039629952000LL,
	72779390658374400LL,
	313029637240320000LL,
	194944796406360000LL,
	1181788075508040000LL,
	1049620756043059200LL,
	97039187544499200LL,
	251793214455182400LL,
	173284263472320000LL,
	787215567032294400LL,
	74801040398884800LL,
	215207875602720000LL,
	1068618416785920000LL,
	106858629141264000LL,
	1246424647801132800LL,
	1100494818423000000LL,
	1454508400625280000LL,
	309899340867916800LL,
	277254821555712000LL,
	151623730538280000LL,
	413199121157222400LL,
	161731979240832000LL,
	475609405082011200LL,
	112201560598327200LL,
	499058678800281600LL,
	335724285940243200LL,
	1543559935357440000LL,
	346568526944640000LL,
	484217720106120000LL,
	447632381253657600LL,
	160287943711896000LL,
	416965258980270000LL,
	200143324310529600LL,
	1640032431317280000LL,
	149602080797769600LL,
	704316683790720000LL,
	388156750177996800LL,
	272922714968904000LL,
	699425595708840000LL,
	291117562633497600LL,
	242597968861248000LL,
	266857765747372800LL,
	1239597363471667200LL,
	623823348500352000LL,
	860831502410880000LL,
	646927916963328000LL,
	1857390699093930000LL,
	224403121196654400LL,
	1007172857820729600LL,
	320575887423792000LL,
	299204161595539200LL,
	1386274107778560000LL,
	1790529525014630400LL,
	485195937722496000LL,
	600429972931588800LL,
	1342897143760972800LL,
	374005201994424000LL,
	533715531494745600LL,
	1902437620328044800LL,
	873352687900492800LL,
	801439718559480000LL,
	1164470250533990400LL,
	854869033130112000LL,
	867287738678961600LL,
	448806242393308800LL,
	800573297242118400LL,
	1364613574844520000LL,
	1067431062989491200LL,
	1212989844306240000LL,
	673209363589963200LL,
	748010403988848000LL,
	1940783750889984000LL,
	1442591493407064000LL,
	1667861035921080000LL,
	1196816646382156800LL,
	1282303549695168000LL,
	897612484786617600LL,
	1122015605983272000LL,
};
long long H2[] = {
	1,
	2,
	3,
	4,
	5,
	6,
	7,
	8,
	9,
	10,
	11,
	12,
	13,
	14,
	15,
	16,
	18,
	20,
	21,
	22,
	24,
	25,
	26,
	27,
	28,
	30,
	32,
	33,
	35,
	36,
	39,
	40,
	42,
	44,
	45,
	48,
	49,
	50,
	52,
	54,
	55,
	56,
	60,
	63,
	64,
	65,
	66,
	70,
	72,
	75,
	77,
	78,
	80,
	81,
	84,
	88,
	90,
	91,
	96,
	98,
	99,
	100,
	104,
	105,
	108,
	110,
	112,
	117,
	120,
	121,
	125,
	126,
	128,
	130,
	132,
	135,
	140,
	143,
	144,
	147,
	150,
	154,
	156,
	160,
	162,
	165,
	168,
	169,
	175,
	176,
	180,
	182,
	189,
	192,
	195,
	196,
	198,
	200,
	208,
	210,
	216,
	220,
	224,
	225,
	231,
	234,
	240,
	242,
	243,
	245,
	250,
	252,
	256,
	260,
	264,
	270,
	273,
	275,
	280,
	286,
	288,
	294,
	297,
	300,
	308,
	312,
	315,
	320,
	324,
	325,
	330,
	336,
	338,
	343,
	350,
	351,
	352,
	360,
	363,
	364,
	375,
	378,
	384,
	385,
	390,
	392,
	396,
	400,
	405,
	416,
	420,
	429,
	432,
	440,
	441,
	448,
	450,
	455,
	462,
	468,
	480,
	484,
	486,
	490,
	495,
	500,
	504,
	507,
	512,
	520,
	525,
	528,
	539,
	540,
	546,
	550,
	560,
	567,
	572,
	576,
	585,
	588,
	594,
	600,
	605,
	616,
	624,
	625,
	630,
	637,
	640,
	648,
	650,
	660,
	672,
	675,
	676,
	686,
	693,
	700,
	702,
	704,
	715,
	720,
	726,
	728,
	729,
	735,
	750,
	756,
	768,
	770,
	780,
	784,
	792,
	800,
	810,
	819,
	825,
	832,
	840,
	845,
	847,
	858,
	864,
	875,
	880,
	882,
	891,
	896,
	900,
	910,
	924,
	936,
	945,
	960,
	968,
	972,
	975,
	980,
	990,
	1000,
	1001,
	1008,
	1014,
	1024,
	1029,
	1040,
	1050,
	1053,
	1056,
	1078,
	1080,
	1089,
	1092,
	1100,
	1120,
	1125,
	1134,
	1144,
	1152,
	1155,
	1170,
	1176,
	1183,
	1188,
	1200,
	1210,
	1215,
	1225,
	1232,
	1248,
	1250,
	1260,
	1274,
	1280,
	1287,
	1296,
	1300,
	1320,
	1323,
	1331,
	1344,
	1350,
	1352,
	1365,
	1372,
	1375,
	1386,
	1400,
	1404,
	1408,
	1430,
	1440,
	1452,
	1456,
	1458,
	1470,
	1485,
	1500,
	1512,
	1521,
	1536,
	1540,
	1560,
	1568,
	1573,
	1575,
	1584,
	1600,
	1617,
	1620,
	1625,
	1638,
	1650,
	1664,
	1680,
	1690,
	1694,
	1701,
	1715,
	1716,
	1728,
	1750,
	1755,
	1760,
	1764,
	1782,
	1792,
	1800,
	1815,
	1820,
	1848,
	1859,
	1872,
	1875,
	1890,
	1911,
	1920,
	1925,
	1936,
	1944,
	1950,
	1960,
	1980,
	2000,
	2002,
	2016,
	2025,
	2028,
	2048,
	2058,
	2079,
	2080,
	2100,
	2106,
	2112,
	2145,
	2156,
	2160,
	2178,
	2184,
	2187,
	2197,
	2200,
	2205,
	2240,
	2250,
	2268,
	2275,
	2288,
	2304,
	2310,
	2340,
	2352,
	2366,
	2376,
	2400,
	2401,
	2420,
	2430,
	2450,
	2457,
	2464,
	2475,
	2496,
	2500,
	2520,
	2535,
	2541,
	2548,
	2560,
	2574,
	2592,
	2600,
	2625,
	2640,
	2646,
	2662,
	2673,
	2688,
	2695,
	2700,
	2704,
	2730,
	2744,
	2750,
	2772,
	2800,
	2808,
	2816,
	2835,
	2860,
	2880,
	2904,
	2912,
	2916,
	2925,
	2940,
	2970,
	3000,
	3003,
	3024,
	3025,
	3042,
	3072,
	3080,
	3087,
	3120,
	3125,
	3136,
	3146,
	3150,
	3159,
	3168,
	3185,
	3200,
	3234,
	3240,
	3250,
	3267,
	3276,
	3300,
	3328,
	3360,
	3375,
	3380,
	3388,
	3402,
	3430,
	3432,
	3456,
	3465,
	3500,
	3510,
	3520,
	3528,
	3549,
	3564,
	3575,
	3584,
	3600,
	3630,
	3640,
	3645,
	3675,
	3696,
	3718,
	3744,
	3750,
	3773,
	3780,
	3822,
	3840,
	3850,
	3861,
	3872,
	3888,
	3900,
	3920,
	3960,
	3969,
	3993,
	4000,
	4004,
	4032,
	4050,
	4056,
	4095,
	4096,
	4116,
	4125,
	4158,
	4160,
	4200,
	4212,
	4224,
	4225,
	4235,
	4290,
	4312,
	4320,
	4356,
	4368,
	4374,
	4375,
	4400,
	4410,
	4455,
	4459,
	4480,
	4500,
	4536,
	4550,
	4563,
	4576,
	4608,
	4620,
	4680,
	4704,
	4719,
	4725,
	4732,
	4752,
	4800,
	4802,
	4840,
	4851,
	4860,
	4875,
	4900,
	4914,
	4928,
	4950,
	4992,
	5000,
	5005,
	5040,
	5070,
	5082,
	5096,
	5103,
	5120,
	5145,
	5148,
	5184,
	5200,
	5250,
	5265,
	5280,
	5292,
	5324,
	5346,
	5376,
	5390,
	5400,
	5408,
	5445,
	5460,
	5488,
	5500,
	5544,
	5577,
	5600,
	5616,
	5625,
	5632,
	5670,
	5720,
	5733,
	5760,
	5775,
	5808,
	5824,
	5832,
	5850,
	5880,
	5915,
	5929,
	5940,
	6000,
	6006,
	6048,
	6050,
	6075,
	6084,
	6125,
	6144,
	6160,
	6174,
	6237,
	6240,
	6250,
	6272,
	6292,
	6300,
	6318,
	6336,
	6370,
	6400,
	6435,
	6468,
	6480,
	6500,
	6534,
	6552,
	6561,
	6600,
	6615,
	6655,
	6656,
	6720,
	6750,
	6760,
	6776,
	6804,
	6825,
	6860,
	6864,
	6875,
	6912,
	6930,
	7000,
	7007,
	7020,
	7040,
	7056,
	7098,
	7128,
	7150,
	7168,
	7200,
	7203,
	7260,
	7280,
	7290,
	7350,
	7371,
	7392,
	7425,
	7436,
	7488,
	7500,
	7546,
	7560,
	7605,
	7623,
	7644,
	7680,
	7700,
	7722,
	7744,
	7776,
	7800,
	7840,
	7875,
	7920,
	7938,
	7986,
	8000,
	8008,
	8019,
	8064,
	8085,
	8100,
	8112,
	8125,
	8190,
	8192,
	8232,
	8250,
	8316,
	8320,
	8400,
	8424,
	8448,
	8450,
	8470,
	8505,
	8575,
	8580,
	8624,
	8640,
	8712,
	8736,
	8748,
	8750,
	8775,
	8800,
	8820,
	8910,
	8918,
	8960,
	9000,
	9009,
	9072,
	9075,
	9100,
	9126,
	9152,
	9216,
	9240,
	9261,
	9360,
	9375,
	9408,
	9438,
	9450,
	9464,
	9477,
	9504,
	9555,
	9600,
	9604,
	9625,
	9680,
	9702,
	9720,
	9750,
	9800,
	9801,
	9828,
	9856,
	9900,
	9984,
	10000,
	10010,
	10080,
	10125,
	10140,
	10164,
	10192,
	10206,
	10240,
	10290,
	10296,
	10368,
	10395,
	10400,
	10500,
	10530,
	10560,
	10584,
	10647,
	10648,
	10692,
	10725,
	10752,
	10780,
	10800,
	10816,
	10890,
	10920,
	10935,
	10976,
	11000,
	11025,
	11088,
	11200,
	11232,
	11250,
	11264,
	11319,
	11340,
	11375,
	11440,
	11466,
	11520,
	11550,
	11583,
	11616,
	11648,
	11664,
	11700,
	11760,
	11830,
	11858,
	11880,
	11907,
	12000,
	12005,
	12012,
	12096,
	12100,
	12150,
	12168,
	12250,
	12285,
	12288,
	12320,
	12348,
	12375,
	12474,
	12480,
	12500,
	12544,
	12600,
	12636,
	12672,
	12675,
	12705,
	12740,
	12800,
	12870,
	12936,
	12960,
	13000,
	13068,
	13104,
	13122,
	13125,
	13200,
	13230,
	13312,
	13365,
	13377,
	13440,
	13475,
	13500,
	13520,
	13552,
	13608,
	13650,
	13689,
	13720,
	13728,
	13750,
	13824,
	13860,
	14000,
	14040,
	14080,
	14112,
	14175,
	14196,
	14256,
	14300,
	14336,
	14400,
	14406,
	14520,
	14553,
	14560,
	14580,
	14625,
	14700,
	14742,
	14784,
	14850,
	14976,
	15000,
	15015,
	15092,
	15120,
	15125,
	15210,
	15246,
	15288,
	15309,
	15360,
	15400,
	15435,
	15444,
	15488,
	15552,
	15600,
	15625,
	15680,
	15750,
	15795,
	15840,
	15876,
	15925,
	16000,
	16016,
	16038,
	16128,
	16170,
	16200,
	16224,
	16250,
	16335,
	16380,
	16384,
	16464,
	16500,
	16632,
	16640,
	16800,
	16848,
	16875,
	16896,
	16900,
	16940,
	17010,
	17150,
	17160,
	17199,
	17248,
	17280,
	17325,
	17424,
	17472,
	17496,
	17500,
	17550,
	17600,
	17640,
	17820,
	17836,
	17920,
	18000,
	18018,
	18144,
	18150,
	18200,
	18225,
	18252,
	18304,
	18375,
	18432,
	18480,
	18522,
	18711,
	18720,
	18750,
	18816,
	18900,
	18928,
	18954,
	19008,
	19110,
	19200,
	19208,
	19250,
	19305,
	19360,
	19404,
	19440,
	19500,
	19600,
	19602,
	19656,
	19683,
	19712,
	19800,
	19845,
	19968,
	20000,
	20020,
	20160,
	20250,
	20280,
	20328,
	20384,
	20412,
	20475,
	20480,
	20580,
	20592,
	20625,
	20736,
	20790,
	20800,
	21000,
	21060,
	21120,
	21168,
	21384,
	21450,
	21504,
	21560,
	21600,
	21609,
	21632,
	21780,
	21840,
	21870,
	21952,
	22000,
	22050,
	22113,
	22176,
	22275,
	22400,
	22464,
	22500,
	22528,
	22680,
	22750,
	22815,
	22869,
	22880,
	22932,
	23040,
	23100,
	23166,
	23232,
	23296,
	23328,
	23400,
	23520,
	23625,
	23760,
	23814,
	24000,
	24024,
	24057,
	24192,
	24200,
	24255,
	24300,
	24336,
	24375,
	24500,
	24570,
	24576,
	24640,
	24696,
	24750,
	24948,
	24960,
	25000,
	25088,
	25200,
	25272,
	25344,
	25480,
	25515,
	25600,
	25740,
	25872,
	25920,
	26000,
	26136,
	26208,
	26244,
	26250,
	26325,
	26400,
	26460,
	26624,
	26730,
	26880,
	27000,
	27040,
	27104,
	27216,
	27225,
	27300,
	27378,
	27440,
	27456,
	27500,
	27648,
	27720,
	27783,
	28000,
	28080,
	28125,
	28160,
	28224,
	28350,
	28431,
	28512,
	28600,
	28672,
	28800,
	29040,
	29106,
	29120,
	29160,
	29250,
	29400,
	29403,
	29484,
	29568,
	29700,
	29952,
	30000,
	30240,
	30375,
	30420,
	30492,
	30576,
	30618,
	30720,
	30800,
	30870,
	30888,
	30976,
	31104,
	31185,
	31200,
	31360,
	31500,
	31590,
	31680,
	31752,
	32000,
	32032,
	32076,
	32256,
	32340,
	32400,
	32448,
	32500,
	32670,
	32760,
	32768,
	32805,
	32928,
	33000,
	33075,
	33264,
	33280,
	33600,
	33696,
	33750,
	33792,
	34020,
	34320,
	34398,
	34496,
	34560,
	34650,
	34749,
	34848,
	34944,
	34992,
	35000,
	35100,
	35200,
	35280,
	35640,
	35721,
	35840,
	36000,
	36288,
	36400,
	36450,
	36504,
	36608,
	36855,
	36864,
	36960,
	37044,
	37125,
	37422,
	37440,
	37500,
	37632,
	37800,
	37908,
	38016,
	38400,
	38720,
	38808,
	38880,
	39000,
	39200,
	39204,
	39312,
	39366,
	39424,
	39600,
	39690,
	39936,
	40000,
	40095,
	40320,
	40500,
	40768,
	40824,
	40950,
	40960,
	41160,
	41184,
	41472,
	41580,
	41600,
	42000,
	42120,
	42240,
	42336,
	42525,
	42768,
	43008,
	43120,
	43200,
	43560,
	43680,
	43740,
	43904,
	44000,
	44100,
	44226,
	44352,
	44550,
	44800,
	44928,
	45000,
	45056,
	45360,
	45760,
	45864,
	45927,
	46080,
	46200,
	46332,
	46464,
	46592,
	46656,
	46800,
	47040,
	47250,
	47385,
	47520,
	47628,
	48000,
	48114,
	48384,
	48600,
	49140,
	49152,
	49280,
	49392,
	49500,
	49896,
	49920,
	50176,
	50400,
	50544,
	50688,
	51030,
	51200,
	51744,
	51840,
	52000,
	52272,
	52416,
	52488,
	52650,
	52800,
	52920,
	53248,
	53460,
	53760,
	54000,
	54432,
	54675,
	54880,
	54912,
	55296,
	55440,
	56000,
	56133,
	56160,
	56320,
	56448,
	56700,
	57024,
	57344,
	57600,
	58080,
	58240,
	58320,
	58800,
	58968,
	59136,
	59400,
	59904,
	60000,
	60480,
	60750,
	61236,
	61440,
	61600,
	61952,
	62208,
	62400,
	62720,
	63000,
	63180,
	63360,
	63504,
	64000,
	64152,
	64512,
	64800,
	65520,
	65536,
	65610,
	65856,
	66000,
	66528,
	66560,
	67200,
	67392,
	67584,
	68040,
	69120,
	69888,
	69984,
	70200,
	70400,
	70560,
	71280,
	71680,
	72000,
	72576,
	72900,
	73728,
	73920,
	74880,
	75264,
	75600,
	76032,
	76800,
	77760,
	78624,
	78848,
	79200,
	79872,
	80000,
	80640,
	81648,
	81920,
	82944,
	83200,
	84240,
	84480,
	84672,
	85536,
	86016,
	86400,
	87480,
	88704,
	89600,
	89856,
	90112,
	90720,
	92160,
	93312,
	94080,
	95040,
	96000,
	96768,
	98304,
	99840,
	100352,
	100800,
	101376,
	102400,
	103680,
	107520,
};


int t;
long long n;

int main(){

	//freopen("input.txt", "r", stdin);

	scanf("%d", &t);
	int cnt = sizeof(H1) / sizeof(long long);
	for (int i = 0; i < t; ++i){
		scanf("%lld", &n);
		for (int i = cnt - 1; i >= 0; --i){
			long long r = H1[i];
			if (r <= 0) continue;
			if (r <= n){
				printf("%lld %lld", r, H2[i]);
				break;
			}
		}
		printf("\n");
	}

	return 0;

}