1	800000	6120000
1	6440000	7640000
1	7960000	8320000
1	8360000	8920000
1	9240000	11960000
1	12040000	12720000
1	13320000	15520000
1	15520000	16560000
1	16960000	18880000
1	18880000	19680000
1	19880000	20480000
1	20680000	21200000
1	22040000	22680000
1	22960000	23440000
1	24040000	25240000
1	25320000	26480000
1	26480000	26920000
1	27000000	28640000
1	28760000	33080000
1	33080000	34760000
1	34840000	36480000
1	36480000	37440000
1	38000000	38840000
1	39040000	39760000
1	39840000	40960000
1	41240000	43160000
1	43200000	43440000
1	44200000	44720000
1	44720000	46360000
1	46440000	50360000
1	50760000	51200000
1	51320000	51880000
1	52040000	53240000
1	53280000	54960000
1	55040000	56720000
1	56800000	58640000
1	58680000	59840000
1	59960000	62120000
1	62200000	62760000
1	62800000	64280000
1	64360000	64840000
1	65040000	65720000
1	65880000	67520000
1	67520000	67760000
1	67840000	69880000
1	70120000	70520000
1	70600000	71080000
1	71080000	73680000
1	73800000	74720000
1	74760000	75720000
1	75880000	78120000
1	78120000	78680000
1	78720000	81760000
1	81800000	83880000
1	83880000	85240000
1	85280000	88880000
1	88920000	90040000
1	90040000	91400000
1	91480000	92720000
1	92840000	93880000
1	94000000	95040000
1	95240000	96840000
1	96960000	98560000
1	98720000	99720000
1	99760000	100920000
1	100920000	101320000
1	101440000	103640000
1	103760000	107760000
1	107760000	108240000
1	108720000	110040000
1	110040000	111400000
1	111440000	112360000
1	112800000	113760000
1	114000000	114800000
1	114920000	116080000
1	116120000	116560000
1	116640000	117960000
1	118040000	121640000
1	124920000	125120000
1	145480000	146080000
1	146560000	148440000
1	149800000	151200000
1	151400000	152040000
1	152040000	153520000
1	153680000	155200000
1	155200000	156360000
1	156680000	159120000
1	159120000	160040000
1	160080000	161440000
1	161760000	162800000
1	162800000	165080000
1	165120000	166840000
1	166880000	167600000
1	167720000	169880000
1	169880000	171440000
1	171600000	172440000
1	172720000	173840000
1	174240000	175040000
1	175040000	176880000
1	176880000	177960000
1	178040000	179440000
1	179840000	180480000
1	180480000	181200000
1	181200000	182040000
1	182080000	182840000
1	182880000	184720000
1	184760000	185720000
1	185760000	186400000
1	186400000	187000000
1	187000000	188720000
1	189160000	190480000
1	190560000	192440000
1	192440000	193040000
1	193120000	194360000
1	194680000	196080000
1	196280000	196720000
1	197400000	198480000
1	198720000	199640000
1	199640000	200880000
1	201400000	201840000
1	202160000	203760000
1	203840000	204400000
1	204560000	206160000
1	206400000	207000000
1	207000000	207800000
1	207800000	211240000
1	211640000	213040000
1	213080000	214160000
1	214360000	215640000
1	215680000	216600000
1	216880000	218240000
1	218240000	219840000
1	220280000	222640000
1	222720000	223680000
1	224040000	225280000
1	225400000	226120000
1	226400000	228560000
1	228640000	231640000
1	231640000	233280000
1	233280000	234360000
1	234400000	236000000
1	236080000	236520000
1	236600000	240000000
1	240160000	243040000
1	243120000	244360000
1	244560000	248956422
2	0	1600000
2	1840000	3680000
2	3680000	6840000
2	6880000	9440000
2	9800000	10680000
2	10760000	11480000
2	11800000	13040000
2	13040000	15600000
2	15600000	16520000
2	16760000	17680000
2	17840000	19920000
2	20360000	20640000
2	20680000	21160000
2	21200000	23720000
2	23800000	25200000
2	25320000	25560000
2	25920000	27320000
2	27400000	28520000
2	28520000	30120000
2	30120000	30720000
2	30720000	32520000
2	32680000	33600000
2	33600000	36760000
2	36960000	37880000
2	37920000	39280000
2	39280000	39760000
2	39800000	41840000
2	41840000	42360000
2	42800000	43600000
2	43600000	44960000
2	44960000	45600000
2	45600000	45960000
2	46000000	46920000
2	46920000	47320000
2	47400000	48520000
2	48600000	50440000
2	50480000	53760000
2	53760000	55680000
2	55680000	57560000
2	57560000	58480000
2	58720000	60720000
2	60720000	61840000
2	61920000	63520000
2	63600000	65200000
2	65240000	65600000
2	65600000	68080000
2	68120000	69360000
2	69400000	70280000
2	70280000	73200000
2	73800000	74600000
2	74680000	75640000
2	75720000	76640000
2	76800000	78280000
2	79240000	79960000
2	80080000	84440000
2	84440000	84880000
2	84960000	85320000
2	85360000	86920000
2	87960000	89280000
2	94160000	95800000
2	95960000	96880000
2	97520000	99520000
2	99520000	100560000
2	100560000	101000000
2	101000000	101200000
2	101240000	101880000
2	102000000	102480000
2	102840000	105280000
2	105280000	106440000
2	106560000	108680000
2	108800000	109760000
2	110600000	111720000
2	111760000	113440000
2	113640000	117800000
2	117960000	119320000
2	119640000	121760000
2	121800000	123920000
2	124000000	127040000
2	127120000	130400000
2	130760000	133880000
2	134040000	134920000
2	134920000	135800000
2	135880000	136400000
2	136400000	137840000
2	137880000	138840000
2	138880000	140840000
2	141080000	143040000
2	143040000	146680000
2	146680000	147920000
2	147920000	149000000
2	149040000	149560000
2	149560000	151440000
2	151600000	152720000
2	152720000	154400000
2	154400000	155320000
2	155360000	157280000
2	157280000	158840000
2	158880000	160000000
2	160000000	161280000
2	161440000	162160000
2	162320000	162840000
2	163160000	164520000
2	164720000	164960000
2	164960000	165960000
2	166120000	168920000
2	168920000	170880000
2	170880000	171480000
2	171600000	172600000
2	172720000	173240000
2	173440000	174400000
2	174680000	177160000
2	177160000	178480000
2	178480000	179800000
2	180040000	182720000
2	182720000	183040000
2	183200000	186680000
2	186800000	187480000
2	187480000	189440000
2	189440000	191000000
2	191040000	191520000
2	191560000	192160000
2	192200000	193720000
2	194080000	195320000
2	195520000	196040000
2	196080000	196760000
2	196840000	197640000
2	197800000	199880000
2	199920000	200840000
2	200880000	202200000
2	202200000	203920000
2	203960000	205960000
2	206160000	207520000
2	207720000	208120000
2	208360000	210240000
2	210440000	212600000
2	212680000	215320000
2	215320000	216040000
2	216080000	219400000
2	219640000	222000000
2	222000000	222640000
2	222680000	223680000
2	223960000	224320000
2	224320000	224720000
2	224800000	227280000
2	227360000	227760000
2	227880000	228600000
2	228680000	229760000
2	229760000	231520000
2	231720000	232520000
2	232520000	234520000
2	234520000	236200000
2	236280000	237800000
2	237840000	238240000
2	239000000	242193529
3	0	3120000
3	3160000	4320000
3	4320000	5200000
3	5240000	8920000
3	8920000	9360000
3	9800000	10280000
3	10320000	11840000
3	12080000	12840000
3	13040000	13480000
3	13680000	14560000
3	15120000	16240000
3	16240000	16560000
3	16560000	17240000
3	17440000	17840000
3	17880000	18840000
3	19000000	19880000
3	20000000	23000000
3	23120000	23800000
3	23880000	24680000
3	24720000	25880000
3	25880000	27000000
3	27680000	28360000
3	28400000	30000000
3	30000000	32480000
3	32960000	33840000
3	33840000	36880000
3	36960000	37240000
3	37240000	37800000
3	37840000	39400000
3	39440000	42520000
3	42880000	44280000
3	44280000	46680000
3	46920000	50280000
3	50320000	51920000
3	52160000	53200000
3	53320000	53920000
3	53920000	56560000
3	56560000	57040000
3	57040000	58560000
3	58640000	59880000
3	59960000	61400000
3	61560000	62200000
3	62600000	63280000
3	63320000	63840000
3	63880000	64440000
3	64480000	66240000
3	66240000	66880000
3	66880000	67760000
3	67840000	69000000
3	69000000	70440000
3	70480000	71680000
3	71720000	73120000
3	73120000	75440000
3	75680000	77280000
3	77320000	78640000
3	78680000	79040000
3	79080000	80760000
3	81280000	83640000
3	84400000	86640000
3	86680000	88160000
3	88200000	91560000
3	93680000	97720000
3	97720000	99800000
3	99800000	100280000
3	100280000	101680000
3	101680000	103800000
3	104560000	105560000
3	105640000	107160000
3	107200000	108960000
3	109440000	111640000
3	111640000	112080000
3	112080000	112560000
3	112560000	113040000
3	113040000	113400000
3	114120000	115200000
3	115200000	115840000
3	115880000	119200000
3	119240000	121360000
3	121520000	122360000
3	122360000	123280000
3	123600000	124720000
3	124920000	125720000
3	125920000	126480000
3	126520000	127560000
3	127560000	128640000
3	128640000	129320000
3	129400000	130000000
3	130120000	132400000
3	132440000	134520000
3	134560000	135640000
3	136040000	137040000
3	137080000	138040000
3	138160000	138960000
3	139400000	141200000
3	141280000	142320000
3	142560000	143040000
3	143040000	143720000
3	143760000	146600000
3	146800000	148960000
3	148960000	150560000
3	151360000	151920000
3	152000000	153000000
3	153000000	154320000
3	154320000	155880000
3	155880000	157200000
3	157520000	158640000
3	158800000	160440000
3	160560000	161440000
3	161480000	163040000
3	164000000	165200000
3	165240000	167360000
3	168000000	169000000
3	169120000	169760000
3	169760000	170880000
3	170880000	171600000
3	171600000	172720000
3	172800000	176480000
3	176840000	179000000
3	179000000	179600000
3	179640000	180640000
3	180760000	182720000
3	183080000	184320000
3	184320000	185320000
3	185600000	186560000
3	186560000	186800000
3	186840000	187160000
3	187200000	187720000
3	187720000	189200000
3	189240000	189920000
3	189960000	190680000
3	191120000	192480000
3	192520000	193600000
3	193600000	194640000
3	194640000	195600000
3	196000000	198295559
4	0	560000
4	720000	3560000
4	3960000	6200000
4	6640000	8960000
4	9360000	12680000
4	12720000	13560000
4	13600000	15200000
4	15440000	16280000
4	16280000	17480000
4	17640000	18600000
4	18640000	20720000
4	20720000	21480000
4	21800000	22360000
4	22400000	22760000
4	22880000	23720000
4	23760000	25400000
4	25840000	27040000
4	27040000	30680000
4	31360000	33000000
4	33360000	36000000
4	36360000	37400000
4	37600000	38760000
4	38880000	40000000
4	40080000	40720000
4	40920000	41240000
4	41240000	41920000
4	42280000	44680000
4	44720000	47440000
4	47640000	49320000
4	51800000	54280000
4	54320000	57040000
4	57040000	60280000
4	60520000	62760000
4	63200000	64640000
4	64680000	67400000
4	67440000	68200000
4	68240000	69640000
4	69680000	70560000
4	70600000	73040000
4	73040000	74160000
4	74360000	74720000
4	74840000	75520000
4	75520000	75880000
4	75960000	77880000
4	77920000	78920000
4	78960000	80240000
4	80320000	81360000
4	81360000	82360000
4	82440000	83280000
4	83480000	85000000
4	85000000	86160000
4	86440000	86880000
4	86880000	89120000
4	89120000	89960000
4	90320000	92240000
4	92440000	94120000
4	94240000	98080000
4	98120000	99080000
4	99080000	99960000
4	100000000	102360000
4	102400000	103120000
4	103200000	103920000
4	103960000	105800000
4	106240000	107920000
4	107960000	108600000
4	108600000	109400000
4	109400000	110000000
4	110000000	110560000
4	110560000	112080000
4	112080000	112640000
4	112800000	114760000
4	114840000	115960000
4	116040000	118440000
4	118560000	119320000
4	119520000	121760000
4	121800000	122960000
4	123000000	123680000
4	123720000	124280000
4	124320000	125280000
4	125320000	127760000
4	128000000	132720000
4	133040000	137040000
4	137080000	139000000
4	139000000	140360000
4	140360000	140800000
4	140920000	143560000
4	144080000	145080000
4	145080000	145640000
4	145720000	147600000
4	147640000	149920000
4	149960000	150240000
4	150240000	151000000
4	151080000	152360000
4	152400000	152760000
4	152760000	153760000
4	153760000	155400000
4	155400000	155960000
4	155960000	157160000
4	157200000	158640000
4	158680000	159480000
4	159480000	162000000
4	162480000	165080000
4	165080000	166120000
4	166160000	168160000
4	168160000	170120000
4	170120000	172920000
4	172960000	174160000
4	174320000	176360000
4	176360000	177040000
4	177120000	179480000
4	180720000	183440000
4	183440000	185160000
4	185440000	186280000
4	186280000	190214555
5	0	5400000
5	5440000	6760000
5	6840000	7880000
5	7880000	10160000
5	10240000	13960000
5	13960000	14360000
5	14680000	15040000
5	15040000	16080000
5	16720000	17200000
5	17200000	18360000
5	18400000	21280000
5	21960000	23160000
5	23160000	24160000
5	24200000	26520000
5	26800000	28800000
5	29000000	31440000
5	31440000	32080000
5	32080000	33400000
5	33440000	34120000
5	34360000	34920000
5	34920000	36000000
5	36040000	37360000
5	37400000	38200000
5	38400000	38920000
5	39120000	39560000
5	39560000	40880000
5	40880000	41840000
5	41840000	43480000
5	43680000	44800000
5	44840000	45800000
5	45840000	46440000
5	49560000	52680000
5	53120000	54440000
5	54520000	55160000
5	55240000	55680000
5	55920000	56200000
5	56200000	57280000
5	57280000	58880000
5	59160000	59800000
5	59800000	60640000
5	60880000	62240000
5	62440000	64080000
5	64160000	65600000
5	65600000	66160000
5	66240000	69600000
5	71320000	73520000
5	73520000	75720000
5	75720000	76240000
5	76320000	76800000
5	76840000	78280000
5	78280000	80400000
5	80680000	81280000
5	81280000	82280000
5	82280000	83640000
5	83680000	86960000
5	87040000	88680000
5	88720000	90680000
5	90800000	91440000
5	91480000	94920000
5	94960000	95440000
5	95480000	97200000
5	97200000	99040000
5	99600000	101760000
5	102560000	103480000
5	103520000	108160000
5	108400000	109480000
5	109680000	110680000
5	110760000	112920000
5	112960000	113560000
5	113600000	115280000
5	115280000	115840000
5	116080000	118960000
5	118960000	119440000
5	119560000	120480000
5	120600000	122160000
5	122160000	123640000
5	123640000	126600000
5	126640000	127520000
5	127520000	128200000
5	128200000	129760000
5	129840000	131160000
5	131440000	132160000
5	132160000	134880000
5	135400000	136200000
5	136240000	137600000
5	138320000	139400000
5	140360000	140720000
5	140760000	141640000
5	141640000	142560000
5	142640000	143840000
5	144200000	146080000
5	146480000	147200000
5	147600000	149600000
5	149600000	150440000
5	150440000	151240000
5	151800000	153960000
5	154000000	154640000
5	154640000	154960000
5	154960000	157160000
5	157160000	159280000
5	159440000	160440000
5	160440000	163440000
5	163480000	165320000
5	165520000	168240000
5	168240000	170160000
5	170800000	171360000
5	171400000	172960000
5	172960000	174000000
5	174000000	174320000
5	174360000	174720000
5	174880000	177560000
5	177920000	181320000
6	40000	1440000
6	1480000	2760000
6	3040000	4040000
6	4200000	4960000
6	5040000	6600000
6	6640000	8080000
6	8240000	10480000
6	10840000	11520000
6	11560000	12640000
6	13320000	13720000
6	13840000	15640000
6	15680000	16240000
6	16240000	17120000
6	17120000	18160000
6	18320000	20080000
6	20520000	24400000
6	24440000	26000000
6	26040000	30200000
6	30440000	31400000
6	31520000	33360000
6	33680000	35280000
6	35480000	36720000
6	37000000	37240000
6	37280000	38720000
6	39320000	41720000
6	41720000	42560000
6	42560000	43160000
6	43240000	43640000
6	43640000	44280000
6	44320000	45960000
6	46040000	47040000
6	47080000	47320000
6	47360000	49880000
6	50080000	50640000
6	50720000	52080000
6	52280000	52680000
6	53120000	53760000
6	53800000	55240000
6	55240000	56320000
6	56320000	58480000
6	60200000	63840000
6	63840000	68480000
6	68600000	70200000
6	70200000	71040000
6	71520000	72160000
6	72600000	73400000
6	73640000	75600000
6	75840000	77440000
6	77480000	78880000
6	78880000	80120000
6	80120000	82120000
6	82240000	83560000
6	83600000	84240000
6	84240000	85640000
6	85680000	87000000
6	87040000	88960000
6	88960000	89840000
6	89840000	90600000
6	90600000	92800000
6	93440000	95200000
6	95320000	96360000
6	96520000	97400000
6	97440000	99320000
6	99400000	100680000
6	100720000	104680000
6	105000000	106320000
6	106360000	107040000
6	107040000	107680000
6	108080000	108520000
6	108520000	109480000
6	109520000	110480000
6	110480000	111000000
6	111240000	111680000
6	111720000	112040000
6	112160000	114000000
6	114040000	116160000
6	116200000	116640000
6	116800000	117640000
6	117920000	118800000
6	118920000	121320000
6	121400000	122320000
6	122360000	123360000
6	123360000	124840000
6	124880000	125120000
6	125280000	126000000
6	126360000	127160000
6	127280000	129440000
6	129480000	130040000
6	130280000	131640000
6	131680000	132800000
6	132840000	134120000
6	134120000	134960000
6	135040000	136320000
6	136960000	137680000
6	137680000	138800000
6	138800000	142120000
6	142160000	143520000
6	143560000	144080000
6	144080000	144520000
6	144560000	145720000
6	145720000	146800000
6	146800000	147320000
6	147360000	148520000
6	148560000	149000000
6	149000000	149520000
6	150040000	150840000
6	150880000	151400000
6	151400000	152400000
6	152400000	154120000
6	154120000	156560000
6	156680000	157280000
6	157280000	158640000
6	158680000	159000000
6	159120000	160640000
6	160680000	161360000
6	161360000	162760000
6	162840000	166120000
6	166200000	167200000
6	167200000	168000000
6	168440000	168880000
6	168880000	170640000
7	0	2240000
7	2720000	5160000
7	5480000	5760000
7	5960000	6520000
7	6520000	8320000
7	8320000	11360000
7	11360000	12400000
7	12520000	13160000
7	13280000	14720000
7	14720000	16600000
7	16680000	17640000
7	17680000	18640000
7	18720000	19680000
7	19680000	20640000
7	20680000	22080000
7	22080000	22520000
7	22520000	23080000
7	23280000	24760000
7	24800000	25160000
7	25160000	27200000
7	27200000	28240000
7	28320000	28840000
7	28920000	30120000
7	30120000	30640000
7	30760000	32480000
7	32720000	35040000
7	35160000	35640000
7	35640000	36360000
7	36360000	37840000
7	37880000	38360000
7	38360000	39800000
7	39880000	41840000
7	41880000	42880000
7	42920000	44000000
7	44040000	45040000
7	45160000	47880000
7	47920000	48160000
7	48160000	49920000
7	50080000	51400000
7	51400000	54720000
7	54720000	58120000
7	60920000	63280000
7	63840000	65520000
7	65720000	67040000
7	67320000	70040000
7	70200000	70840000
7	70840000	72800000
7	73280000	74760000
7	75520000	76400000
7	76640000	79240000
7	79240000	80040000
7	80040000	81440000
7	81480000	82800000
7	83360000	83760000
7	83800000	85040000
7	85040000	85880000
7	85880000	87280000
7	87280000	88120000
7	88200000	90120000
7	90120000	91040000
7	91080000	91800000
7	91880000	92480000
7	92560000	93080000
7	93160000	94240000
7	94400000	95720000
7	95720000	98240000
7	98240000	98880000
7	98880000	99440000
7	99440000	100240000
7	100880000	102480000
7	102680000	104200000
7	104200000	104920000
7	104920000	105520000
7	105600000	106040000
7	106160000	106760000
7	106760000	108520000
7	108560000	111720000
7	111720000	112480000
7	112520000	112920000
7	113000000	113760000
7	113760000	116120000
7	116120000	117160000
7	117280000	118240000
7	118280000	120720000
7	120800000	122040000
7	122080000	123440000
7	123440000	123920000
7	124000000	124960000
7	125040000	127560000
7	127640000	128280000
7	128360000	130040000
7	130040000	130840000
7	130840000	131560000
7	131640000	135520000
7	135680000	137880000
7	138040000	138840000
7	139360000	140400000
7	140680000	142400000
7	142600000	143560000
7	143840000	148520000
7	148560000	149080000
7	149120000	151040000
7	151240000	152800000
7	152840000	154000000
7	154160000	154800000
7	154800000	155800000
7	155800000	157400000
7	157440000	159345973
8	120000	2040000
8	2480000	6400000
8	6400000	7160000
8	8200000	9840000
8	9840000	12040000
8	12560000	13400000
8	13400000	13680000
8	13680000	14880000
8	15320000	17160000
8	17200000	17920000
8	17920000	18800000
8	18880000	19360000
8	19400000	20200000
8	20400000	22040000
8	22160000	22600000
8	22600000	25080000
8	25520000	26120000
8	26640000	27280000
8	27640000	30160000
8	30200000	30680000
8	30840000	31200000
8	31200000	32200000
8	32280000	33600000
8	33640000	37720000
8	37760000	38760000
8	38800000	39000000
8	39120000	41520000
8	41880000	42400000
8	42400000	44000000
8	45960000	47960000
8	48040000	48960000
8	48960000	52520000
8	52560000	54560000
8	54720000	57360000
8	57400000	58560000
8	58680000	60400000
8	60400000	61160000
8	61160000	61480000
8	61600000	63200000
8	63320000	64520000
8	64520000	65600000
8	65600000	66640000
8	66640000	67520000
8	67800000	69640000
8	70000000	70680000
8	70680000	72200000
8	72240000	72960000
8	73000000	73240000
8	73280000	74920000
8	75120000	78400000
8	78440000	79640000
8	79680000	80600000
8	80600000	81760000
8	81920000	85120000
8	85280000	86600000
8	86600000	89680000
8	89720000	91160000
8	91160000	94000000
8	94000000	94480000
8	94720000	95280000
8	95280000	96200000
8	96240000	98120000
8	98120000	100120000
8	100120000	100560000
8	100560000	102880000
8	103080000	103520000
8	103560000	104480000
8	104520000	105840000
8	105880000	106600000
8	106960000	107800000
8	107800000	108720000
8	108880000	109320000
8	109360000	109720000
8	109760000	110880000
8	111400000	111880000
8	111880000	112600000
8	112720000	113440000
8	114480000	117320000
8	117320000	119440000
8	119480000	119800000
8	119800000	120960000
8	120960000	122640000
8	122680000	123040000
8	123240000	124480000
8	124480000	125080000
8	125080000	125720000
8	125720000	126800000
8	126800000	127680000
8	127720000	129760000
8	130080000	130680000
8	130720000	132720000
8	132720000	133480000
8	133480000	134880000
8	134880000	135760000
8	135840000	138080000
8	138120000	138720000
8	138760000	140440000
8	140640000	141360000
8	141440000	143280000
8	143560000	145138636
9	0	4280000
9	4360000	6800000
9	6800000	10000000
9	10000000	12600000
9	12680000	14880000
9	15200000	15640000
9	15720000	16960000
9	17080000	17480000
9	17520000	18200000
9	18240000	19480000
9	19480000	21200000
9	21200000	21800000
9	21800000	22240000
9	22240000	23880000
9	24440000	26520000
9	26720000	28120000
9	28760000	32360000
9	32360000	33000000
9	33000000	33280000
9	33280000	36560000
9	36640000	39600000
9	68320000	69040000
9	69040000	69920000
9	69920000	70600000
9	70640000	72000000
9	72040000	72640000
9	72840000	73080000
9	73200000	74760000
9	75160000	76400000
9	76400000	77160000
9	77160000	78200000
9	78360000	80160000
9	80240000	83560000
9	83920000	84320000
9	84360000	85800000
9	86320000	87920000
9	87920000	89240000
9	89320000	90120000
9	90120000	90880000
9	90880000	92080000
9	92120000	92800000
9	92920000	93960000
9	94000000	94240000
9	94360000	95160000
9	95200000	97640000
9	97680000	98800000
9	98800000	100600000
9	100640000	101440000
9	101560000	104760000
9	104760000	105520000
9	105800000	107200000
9	107400000	109360000
9	109560000	110160000
9	110400000	111360000
9	111360000	114320000
9	114400000	116680000
9	117000000	120560000
9	120560000	122800000
9	123000000	123360000
9	123400000	124760000
9	124840000	126680000
9	126920000	128120000
9	128160000	129000000
9	129120000	129640000
9	129640000	130400000
9	130440000	130680000
9	130680000	134160000
9	134520000	138200000
10	40000	1080000
10	1120000	3080000
10	3120000	4800000
10	4800000	5920000
10	6400000	7480000
10	7520000	9320000
10	9320000	11400000
10	11480000	11760000
10	11760000	13120000
10	13360000	15200000
10	15400000	16800000
10	16800000	17400000
10	17840000	20840000
10	20840000	23120000
10	23120000	24560000
10	24600000	25720000
10	25840000	28400000
10	28640000	29360000
10	29480000	32040000
10	32760000	35080000
10	35080000	35560000
10	35600000	38400000
10	38920000	39560000
10	41680000	46440000
10	46960000	47480000
10	48160000	49920000
10	50160000	50680000
10	50760000	52560000
10	52800000	55000000
10	55520000	58120000
10	58400000	60680000
10	60720000	62400000
10	62400000	63120000
10	63160000	63840000
10	63880000	67800000
10	67800000	68360000
10	68400000	70400000
10	70480000	71280000
10	71280000	71800000
10	71920000	73720000
10	73800000	75280000
10	75280000	76520000
10	76600000	77120000
10	77160000	77800000
10	78040000	79720000
10	80240000	84120000
10	84240000	86960000
10	87480000	89240000
10	89400000	89720000
10	89760000	91720000
10	91760000	92480000
10	92600000	93520000
10	93720000	94560000
10	94600000	95040000
10	95200000	95640000
10	95680000	97640000
10	97760000	99640000
10	99720000	100920000
10	101000000	101800000
10	101800000	102120000
10	102120000	102640000
10	102720000	103440000
10	103680000	104360000
10	104360000	106200000
10	106600000	109880000
10	109880000	112040000
10	112120000	112440000
10	112440000	113680000
10	113680000	114160000
10	114280000	114800000
10	115160000	116520000
10	116640000	117160000
10	117200000	119040000
10	119200000	120760000
10	120840000	121960000
10	122240000	122600000
10	122800000	123920000
10	124000000	124800000
10	125840000	128120000
10	128240000	130120000
10	130200000	133797422
11	160000	3280000
11	3560000	4120000
11	4120000	6360000
11	6360000	8600000
11	8640000	10760000
11	10760000	12280000
11	12320000	13480000
11	13800000	14280000
11	14440000	15240000
11	15240000	17080000
11	17560000	18800000
11	18920000	20120000
11	20200000	22840000
11	22880000	26280000
11	26280000	27520000
11	27520000	29360000
11	29400000	30160000
11	30280000	30960000
11	31360000	32280000
11	32800000	33760000
11	33800000	34480000
11	34520000	34920000
11	34920000	35440000
11	35560000	36560000
11	36760000	38880000
11	39480000	41440000
11	41520000	43320000
11	43320000	45800000
11	45800000	48160000
11	48160000	50040000
11	50360000	50840000
11	54520000	55760000
11	55880000	57280000
11	57280000	58560000
11	58560000	59720000
11	59800000	61240000
11	61240000	64240000
11	64840000	67480000
11	67920000	70240000
11	70440000	71600000
11	71800000	73280000
11	73400000	76680000
11	76720000	77040000
11	77160000	78600000
11	78600000	79120000
11	79120000	81520000
11	81600000	82480000
11	82680000	83800000
11	83840000	84560000
11	84720000	85600000
11	85600000	86320000
11	86440000	86880000
11	86920000	87360000
11	87440000	89680000
11	90080000	93680000
11	93840000	94440000
11	94520000	95800000
11	95840000	96440000
11	96440000	99040000
11	99040000	99760000
11	99800000	100560000
11	100560000	102040000
11	102280000	102680000
11	103120000	105920000
11	106080000	107840000
11	107960000	108680000
11	108680000	109760000
11	110200000	111520000
11	111520000	111880000
11	112280000	113760000
11	113840000	114600000
11	114640000	116720000
11	116760000	117200000
11	117400000	118120000
11	118120000	119000000
11	119080000	120120000
11	120240000	121120000
11	121240000	121640000
11	121640000	123080000
11	123080000	124600000
11	124640000	125880000
11	125880000	126280000
11	126320000	127400000
11	128000000	128960000
11	129080000	129760000
11	129840000	130200000
11	130400000	130920000
11	130920000	133080000
11	133080000	135086622
12	0	1600000
12	1640000	2640000
12	3040000	3840000
12	3840000	6840000
12	6880000	8200000
12	8400000	9280000
12	9560000	11520000
12	11520000	12080000
12	12080000	12360000
12	12360000	12760000
12	12800000	13240000
12	13240000	14160000
12	14200000	15920000
12	15960000	18080000
12	18120000	19360000
12	19680000	20640000
12	21240000	22040000
12	22080000	25160000
12	25160000	26040000
12	26040000	27000000
12	27000000	27720000
12	27720000	29000000
12	29080000	31120000
12	31280000	32720000
12	32760000	34320000
12	34360000	34720000
12	37240000	39280000
12	39320000	43360000
12	43920000	45120000
12	45120000	46000000
12	46000000	47720000
12	47880000	48680000
12	49080000	51960000
12	52160000	53000000
12	53520000	55680000
12	55960000	56480000
12	56720000	57760000
12	57960000	59160000
12	59200000	62240000
12	62240000	63600000
12	63800000	64400000
12	64440000	64760000
12	64760000	66920000
12	67240000	68200000
12	68320000	68760000
12	68800000	69120000
12	69320000	71920000
12	72000000	74560000
12	74640000	75320000
12	75480000	76600000
12	76600000	77000000
12	77040000	77960000
12	77960000	79400000
12	79480000	80280000
12	80360000	81320000
12	81640000	82320000
12	82360000	84760000
12	84840000	85080000
12	85080000	85920000
12	85960000	88040000
12	88080000	89480000
12	89520000	91320000
12	91360000	92760000
12	92760000	93440000
12	93440000	94120000
12	94120000	95000000
12	95080000	95960000
12	96040000	96520000
12	96520000	98400000
12	99000000	100000000
12	100120000	101280000
12	101400000	102840000
12	102880000	103640000
12	103840000	105120000
12	105400000	106200000
12	106360000	107000000
12	107080000	107640000
12	107680000	108520000
12	108560000	109080000
12	109200000	109800000
12	110000000	112440000
12	112480000	115920000
12	115920000	117160000
12	117200000	118400000
12	118400000	120200000
12	120280000	123680000
12	123720000	124960000
12	125000000	127720000
12	128480000	132440000
12	132840000	133275309
13	18440000	21520000
13	21560000	23080000
13	23360000	23920000
13	24000000	24320000
13	25040000	26080000
13	26160000	26920000
13	26920000	27320000
13	27360000	28000000
13	28320000	29400000
13	29440000	30120000
13	30120000	31080000
13	31200000	31760000
13	31840000	33760000
13	33880000	35840000
13	35960000	36800000
13	37040000	39000000
13	39000000	39640000
13	39680000	41080000
13	41320000	42160000
13	42280000	43880000
13	43880000	45360000
13	45400000	46400000
13	46440000	46760000
13	46760000	48000000
13	48080000	48800000
13	49280000	49640000
13	49640000	52480000
13	52560000	55080000
13	55600000	57560000
13	57600000	59320000
13	59360000	60440000
13	60560000	62000000
13	62080000	63800000
13	64440000	65560000
13	65640000	67440000
13	67480000	69480000
13	69520000	70600000
13	70600000	72720000
13	72720000	75520000
13	75560000	77000000
13	77040000	77560000
13	77560000	79360000
13	79560000	81040000
13	81080000	84720000
13	84840000	85840000
13	86680000	91760000
13	91880000	94640000
13	94640000	95480000
13	95960000	97000000
13	97040000	97800000
13	97800000	98840000
13	99120000	99440000
13	99600000	100560000
13	100680000	102880000
13	102880000	107200000
13	107200000	108200000
13	108320000	108920000
13	108920000	110160000
13	110200000	114364328
14	16040000	21560000
14	21600000	22880000
14	23560000	24320000
14	24480000	25160000
14	25240000	28680000
14	28680000	29520000
14	29560000	30560000
14	30560000	31400000
14	31440000	32520000
14	32560000	34520000
14	34560000	35840000
14	35880000	36560000
14	37200000	39440000
14	39440000	41800000
14	42120000	45320000
14	45360000	47720000
14	47800000	49560000
14	49600000	50880000
14	50920000	52120000
14	53320000	54480000
14	54520000	54920000
14	55160000	56480000
14	56480000	58080000
14	58200000	59520000
14	59600000	59920000
14	59920000	61280000
14	61280000	61880000
14	61880000	63360000
14	63360000	64520000
14	65120000	66120000
14	66320000	67360000
14	67360000	68840000
14	69240000	69480000
14	69520000	71000000
14	71040000	72480000
14	72480000	72960000
14	73040000	75680000
14	75680000	76840000
14	76880000	77800000
14	77840000	81520000
14	81560000	83120000
14	83280000	86080000
14	86200000	87920000
14	87920000	88440000
14	88560000	90280000
14	90280000	91200000
14	91640000	92040000
14	92080000	92800000
14	92800000	93560000
14	94000000	95440000
14	95560000	96560000
14	96560000	99360000
14	99640000	101680000
14	101760000	102320000
14	102520000	105480000
14	105720000	107043718
15	20160000	28320000
15	28840000	30120000
15	30600000	31520000
15	31720000	32160000
15	32600000	34400000
15	34600000	34960000
15	35000000	37960000
15	37960000	38720000
15	38720000	40320000
15	40480000	43680000
15	43840000	44840000
15	45160000	45440000
15	45680000	48320000
15	48320000	50360000
15	50360000	50960000
15	51000000	52160000
15	52240000	52760000
15	52760000	53760000
15	53800000	55480000
15	56080000	57560000
15	57560000	58840000
15	58960000	59680000
15	59680000	63080000
15	63120000	64160000
15	64160000	65200000
15	65320000	66360000
15	66560000	68240000
15	68560000	68880000
15	69000000	69400000
15	69440000	70640000
15	70920000	72640000
15	72680000	74320000
15	75320000	77920000
15	77920000	80400000
15	80480000	81000000
15	81440000	82320000
15	82520000	84200000
15	84520000	85840000
15	85840000	88880000
15	89040000	90920000
15	91040000	93040000
15	93040000	94160000
15	94560000	98400000
15	98440000	99240000
15	99240000	99800000
15	99880000	101991189
16	0	2000000
16	2240000	5080000
16	5080000	8520000
16	8560000	10920000
16	10960000	11880000
16	12040000	12840000
16	12840000	13920000
16	13920000	14720000
16	14920000	16240000
16	16520000	18120000
16	18760000	19440000
16	19560000	20440000
16	20760000	21400000
16	21560000	22440000
16	22720000	23480000
16	23680000	24520000
16	24520000	25040000
16	25240000	28320000
16	29600000	30040000
16	30320000	30960000
16	30960000	32040000
16	34000000	36360000
16	46360000	48640000
16	48680000	49960000
16	50000000	52000000
16	52040000	53520000
16	53520000	55720000
16	55920000	56360000
16	56520000	58640000
16	58760000	62160000
16	62200000	63280000
16	63360000	66880000
16	66880000	70120000
16	70960000	74280000
16	74400000	75160000
16	75160000	78080000
16	78080000	80960000
16	81280000	81760000
16	81880000	85000000
16	85240000	88440000
16	88720000	90120000
17	40000	2720000
17	2760000	3680000
17	4120000	4920000
17	5160000	5480000
17	5480000	6640000
17	6640000	7200000
17	7360000	8200000
17	8320000	8800000
17	9000000	9560000
17	9800000	12000000
17	12240000	12720000
17	13120000	15560000
17	16000000	19040000
17	19200000	19960000
17	20000000	21680000
17	22080000	22760000
17	26600000	28360000
17	28560000	30640000
17	30920000	32040000
17	32440000	36240000
17	36480000	37920000
17	38760000	41680000
17	41880000	43280000
17	43360000	45440000
17	45600000	46320000
17	46680000	50360000
17	50480000	51280000
17	51280000	54920000
17	54960000	56800000
17	56960000	57840000
17	57840000	58480000
17	58520000	59160000
17	59200000	59960000
17	60120000	60680000
17	60680000	62240000
17	62480000	63440000
17	63920000	64760000
17	64920000	66160000
17	66200000	67360000
17	67360000	67720000
17	68040000	69280000
17	69360000	70560000
17	70640000	72600000
17	72720000	73400000
17	73480000	74200000
17	74360000	74800000
17	74960000	76520000
17	76720000	78120000
17	78440000	79720000
17	79720000	81720000
17	82240000	83257441
18	0	2600000
18	2640000	3240000
18	3240000	3680000
18	3680000	5080000
18	5080000	7080000
18	7200000	8560000
18	8640000	9040000
18	9040000	9520000
18	9960000	10560000
18	10760000	12120000
18	12280000	12960000
18	13160000	15440000
18	20920000	22720000
18	22800000	24160000
18	24440000	26200000
18	26720000	28200000
18	28520000	30960000
18	30960000	32040000
18	32120000	32600000
18	32600000	34840000
18	34920000	36800000
18	37400000	39760000
18	40200000	41960000
18	41960000	43600000
18	43600000	46120000
18	46120000	47760000
18	47760000	48480000
18	48680000	49480000
18	49480000	50480000
18	51080000	54160000
18	54400000	55000000
18	55120000	56640000
18	56640000	57600000
18	57600000	59160000
18	59400000	61520000
18	61520000	62160000
18	62160000	63480000
18	63480000	66920000
18	67160000	68760000
18	68800000	70520000
18	70520000	72680000
18	72680000	74120000
18	74160000	74560000
18	74560000	76760000
18	76800000	77680000
18	78040000	80373285
19	240000	4520000
19	4640000	8560000
19	8760000	9840000
19	10480000	12960000
19	13160000	18000000
19	18400000	18960000
19	19520000	24440000
19	27240000	27640000
19	27760000	29480000
19	29720000	32600000
19	33120000	35640000
19	36120000	37880000
19	37920000	38360000
19	39040000	41920000
19	42080000	42280000
19	43760000	44560000
19	45680000	47760000
19	47920000	48640000
19	48640000	49480000
19	50520000	54080000
19	54480000	55680000
19	55680000	57080000
19	57240000	58617616
20	40000	3680000
20	4080000	5120000
20	5200000	6120000
20	6120000	7920000
20	8000000	8760000
20	8880000	11560000
20	11600000	12920000
20	12920000	13840000
20	14080000	17440000
20	17480000	18040000
20	18600000	20040000
20	20080000	21640000
20	21680000	22200000
20	22320000	23640000
20	23800000	26400000
20	28520000	31040000
20	31520000	33360000
20	33360000	34160000
20	34280000	34800000
20	34800000	35440000
20	35520000	36920000
20	37040000	38440000
20	38600000	41680000
20	41720000	43440000
20	43440000	44120000
20	44200000	45800000
20	46000000	47640000
20	47640000	48920000
20	48960000	49960000
20	50160000	50760000
20	50800000	52080000
20	52200000	53560000
20	53560000	54680000
20	54680000	56360000
20	56520000	58200000
20	58200000	59520000
20	59600000	61960000
20	62000000	64444167
21	12960000	15640000
21	15880000	17600000
21	17640000	17920000
21	18000000	20960000
21	21000000	22920000
21	23040000	25560000
21	25560000	26720000
21	26720000	28960000
21	29080000	29400000
21	29400000	29880000
21	30240000	31600000
21	31640000	32280000
21	32320000	33480000
21	33640000	34360000
21	34480000	36120000
21	36400000	36920000
21	37040000	37560000
21	37640000	39480000
21	39480000	43040000
21	43800000	44120000
21	44240000	46709983
22	15920000	17520000
22	17800000	18200000
22	18960000	21120000
22	21560000	23880000
22	24000000	24600000
22	24640000	27800000
22	27840000	29280000
22	29360000	31400000
22	31640000	35240000
22	35280000	36520000
22	36520000	37520000
22	37800000	40040000
22	40040000	40400000
22	40400000	41320000
22	41680000	42520000
22	42640000	43120000
22	43200000	43880000
22	43960000	44680000
22	45240000	46360000
22	46760000	50818468
23	200000	2840000
23	3000000	7920000
23	8000000	8720000
23	8800000	9760000
23	10160000	10680000
23	10800000	11120000
23	11120000	12760000
23	12800000	13480000
23	13480000	16720000
23	16720000	18240000
23	18360000	20120000
23	20200000	21760000
23	22280000	23640000
23	23680000	27320000
23	27520000	30560000
23	30560000	32280000
23	32400000	34320000
23	34560000	37120000
23	37440000	38200000
23	38320000	40560000
23	40640000	41280000
23	41520000	47120000
23	47160000	49160000
23	49600000	52480000
23	52960000	58560000
23	62480000	65520000
23	65560000	68160000
23	68840000	69400000
23	69440000	71680000
23	71840000	72760000
23	72960000	74120000
23	74640000	78120000
23	78400000	83800000
23	83880000	85560000
23	85760000	89520000
23	92080000	102040000
23	104400000	108040000
23	108160000	109440000
23	109640000	110440000
23	111760000	115720000
23	115880000	118280000
23	118320000	119960000
23	120800000	123560000
23	123840000	129400000
23	129480000	130960000
23	130960000	131680000
23	131800000	133680000
23	134440000	135600000
23	135880000	136920000
23	137240000	138760000
23	138760000	140680000
23	140760000	143400000
23	143560000	145240000
23	145280000	149560000
23	149920000	150760000
23	150760000	152840000
23	152920000	156040895
24	2760000	3120000
24	6480000	10280000
24	11720000	17480000
24	18840000	26640000