timus Samoe-Slozhnoe-Chislo 1748 problem 0_o precalca

1748_3.cpp

#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;
	
}