1	800000	2400000
1	2400000	6200000
1	6480000	7960000
1	7960000	8320000
1	8360000	8880000
1	9240000	10440000
1	10480000	11000000
1	11040000	11800000
1	12080000	12680000
1	12720000	15520000
1	15520000	16000000
1	16080000	16520000
1	16920000	18880000
1	18880000	19240000
1	19320000	19680000
1	19880000	20520000
1	20680000	21200000
1	21200000	22640000
1	22680000	22960000
1	22960000	23760000
1	23760000	24840000
1	24840000	25240000
1	25320000	25800000
1	25880000	26480000
1	26480000	26920000
1	26920000	28520000
1	28680000	30960000
1	31160000	33080000
1	33120000	33480000
1	33480000	34840000
1	35160000	36080000
1	36080000	36440000
1	36480000	37440000
1	38040000	38880000
1	39040000	39760000
1	39800000	40040000
1	40040000	40440000
1	40600000	41000000
1	41240000	42760000
1	42760000	43200000
1	43200000	43440000
1	43720000	43960000
1	44040000	44720000
1	44760000	45560000
1	45600000	46320000
1	46400000	50360000
1	50360000	50720000
1	50760000	51240000
1	51320000	51800000
1	52040000	53240000
1	53280000	53840000
1	54000000	54920000
1	55040000	56800000
1	56800000	58480000
1	58680000	59840000
1	59960000	62120000
1	62440000	62760000
1	62800000	64280000
1	64280000	65000000
1	65120000	65680000
1	65720000	66240000
1	66240000	66720000
1	66760000	67160000
1	67520000	67800000
1	67840000	68440000
1	68520000	70520000
1	71080000	74720000
1	74760000	75240000
1	75720000	77160000
1	77160000	77720000
1	78120000	78640000
1	78680000	83880000
1	83880000	85280000
1	85280000	86360000
1	86360000	88880000
1	88920000	90040000
1	90080000	91400000
1	91480000	91960000
1	91960000	92680000
1	92840000	93880000
1	93920000	94480000
1	94480000	95120000
1	95240000	96720000
1	96880000	98560000
1	98760000	99760000
1	99760000	101360000
1	101440000	103600000
1	103760000	108240000
1	108520000	110040000
1	110040000	112360000
1	112400000	112680000
1	112720000	113080000
1	113080000	113720000
1	113960000	114320000
1	114800000	116600000
1	116640000	117960000
1	118000000	121600000
1	145480000	146080000
1	146840000	148440000
1	149800000	150240000
1	150240000	151200000
1	151280000	152040000
1	152040000	153520000
1	153800000	154000000
1	154320000	155200000
1	155200000	156920000
1	157080000	159120000
1	159160000	161160000
1	161440000	162800000
1	162800000	163360000
1	163360000	165160000
1	165360000	165600000
1	165600000	166760000
1	166840000	167680000
1	167720000	168080000
1	168320000	169800000
1	169840000	171440000
1	171480000	172440000
1	172520000	174200000
1	174240000	175040000
1	175040000	176840000
1	176880000	177960000
1	177960000	179400000
1	179840000	180200000
1	180240000	180480000
1	180480000	181200000
1	181200000	182840000
1	182840000	184760000
1	184760000	185680000
1	185720000	186360000
1	186400000	187000000
1	187000000	188800000
1	189560000	190480000
1	190480000	192440000
1	192480000	193080000
1	193120000	196760000
1	197400000	198720000
1	198720000	199600000
1	199640000	200560000
1	200600000	201400000
1	201440000	202160000
1	202160000	203000000
1	203000000	203840000
1	203840000	204520000
1	204520000	205560000
1	205760000	206160000
1	206480000	206920000
1	207080000	207520000
1	207640000	208240000
1	208280000	209760000
1	209760000	210320000
1	210400000	211280000
1	211680000	212440000
1	212480000	213040000
1	213080000	214200000
1	214200000	215600000
1	215640000	216600000
1	216760000	218240000
1	218280000	219960000
1	220160000	220720000
1	220800000	222720000
1	222720000	223120000
1	223120000	223680000
1	224120000	225000000
1	225440000	226040000
1	226400000	228560000
1	228640000	229520000
1	229560000	230360000
1	230640000	231240000
1	231320000	233320000
1	233400000	234360000
1	234480000	235120000
1	235160000	235440000
1	235520000	236080000
1	236080000	239960000
1	240000000	240720000
1	240720000	243040000
1	243120000	244480000
1	244560000	246800000
1	246960000	247360000
1	247400000	248956422
2	0	1840000
2	1920000	3680000
2	3680000	7000000
2	7080000	8800000
2	8800000	9120000
2	9120000	9400000
2	9440000	10040000
2	10080000	10720000
2	10720000	11120000
2	11160000	11480000
2	11680000	13040000
2	13040000	15600000
2	15600000	17680000
2	17720000	20640000
2	20680000	23800000
2	23800000	25200000
2	25240000	25680000
2	25840000	27320000
2	27360000	28840000
2	28920000	30120000
2	30120000	30720000
2	30720000	32200000
2	32520000	33600000
2	33600000	36320000
2	36320000	36960000
2	37080000	37920000
2	37920000	38800000
2	38880000	39760000
2	39760000	41840000
2	41840000	42360000
2	42800000	43600000
2	43600000	44960000
2	44960000	45600000
2	45600000	45960000
2	45960000	46920000
2	46960000	47400000
2	47400000	48480000
2	48560000	50480000
2	50480000	53800000
2	53800000	55640000
2	55640000	56040000
2	56160000	57560000
2	57640000	61040000
2	61040000	61880000
2	61880000	63560000
2	63560000	64520000
2	64560000	65040000
2	65240000	65600000
2	65600000	68080000
2	68120000	68920000
2	68960000	70280000
2	70280000	73680000
2	73760000	74440000
2	74600000	75720000
2	75720000	79880000
2	79920000	80600000
2	82040000	84440000
2	84440000	84880000
2	84960000	85320000
2	85360000	86200000
2	86200000	86840000
2	88000000	89240000
2	94720000	95760000
2	96000000	97120000
2	97520000	99120000
2	99320000	100560000
2	100600000	101000000
2	101000000	101240000
2	101240000	101880000
2	102000000	102640000
2	102800000	104840000
2	105040000	106400000
2	106640000	108680000
2	108760000	109760000
2	110600000	111720000
2	111840000	112360000
2	112600000	113400000
2	113640000	113960000
2	113960000	117760000
2	117800000	119520000
2	119640000	120200000
2	120240000	120680000
2	120680000	121120000
2	121360000	121800000
2	121800000	127000000
2	127080000	127880000
2	128040000	130400000
2	132200000	133880000
2	133880000	134920000
2	134920000	135800000
2	135880000	137840000
2	137840000	138840000
2	138880000	143040000
2	143040000	146720000
2	146720000	147920000
2	147920000	149560000
2	149560000	150480000
2	150480000	151480000
2	151600000	152720000
2	152720000	157360000
2	157440000	158840000
2	158880000	159800000
2	160040000	161280000
2	161400000	162360000
2	162640000	164640000
2	164720000	165280000
2	165360000	165920000
2	166120000	169000000
2	169320000	170920000
2	170920000	171520000
2	171520000	172120000
2	172160000	172560000
2	172560000	173240000
2	173320000	174400000
2	174560000	175160000
2	175200000	176680000
2	177160000	177920000
2	178080000	178480000
2	178760000	179800000
2	179960000	181080000
2	181080000	182160000
2	182160000	183040000
2	183240000	186480000
2	186480000	186680000
2	186840000	187480000
2	187480000	188520000
2	188520000	189640000
2	189720000	191000000
2	191040000	191520000
2	191560000	192320000
2	192320000	195280000
2	195320000	196040000
2	196080000	196800000
2	196800000	197520000
2	197800000	199880000
2	199920000	200880000
2	200880000	201640000
2	201760000	202280000
2	202520000	203920000
2	203960000	206160000
2	206160000	208280000
2	208360000	210280000
2	210440000	212600000
2	212640000	213160000
2	213240000	215320000
2	215320000	216040000
2	216120000	216480000
2	216480000	219400000
2	219560000	222640000
2	222640000	223960000
2	223960000	224720000
2	224760000	225640000
2	225640000	227120000
2	227320000	229760000
2	229760000	230840000
2	231040000	231480000
2	231720000	232520000
2	232520000	233280000
2	233840000	234520000
2	234520000	235120000
2	235120000	235760000
2	235760000	236200000
2	236280000	237080000
2	237080000	237760000
2	237800000	238280000
2	238320000	242193529
3	0	3880000
3	4280000	5200000
3	5240000	8440000
3	8440000	8640000
3	8720000	9600000
3	9800000	10280000
3	10320000	11840000
3	12080000	12920000
3	13000000	14960000
3	15120000	16280000
3	16280000	16560000
3	16560000	17240000
3	17440000	17840000
3	17880000	18440000
3	20320000	22240000
3	22880000	23920000
3	24000000	24680000
3	24760000	27040000
3	27080000	28360000
3	28560000	30000000
3	30040000	30760000
3	30760000	32720000
3	32960000	33840000
3	33840000	36720000
3	36960000	37400000
3	37400000	37840000
3	37840000	38000000
3	38040000	39360000
3	39400000	42560000
3	42880000	44320000
3	44520000	44760000
3	45000000	46680000
3	46920000	47400000
3	47440000	47800000
3	47840000	48200000
3	48200000	50280000
3	50320000	51920000
3	51960000	52720000
3	52720000	53080000
3	53280000	56560000
3	56680000	57520000
3	57560000	58160000
3	58320000	59880000
3	60000000	61360000
3	61560000	62320000
3	62600000	63280000
3	63320000	63840000
3	63840000	64520000
3	64520000	65320000
3	65360000	65760000
3	65760000	66240000
3	66240000	66880000
3	66920000	68960000
3	69000000	70000000
3	70040000	71720000
3	71720000	73080000
3	73120000	75520000
3	75680000	76640000
3	77000000	78640000
3	78640000	79560000
3	79600000	82160000
3	86640000	88160000
3	88200000	91560000
3	93720000	97720000
3	97760000	98440000
3	98560000	99800000
3	99800000	100280000
3	100320000	101720000
3	101720000	102240000
3	102240000	104120000
3	104240000	105360000
3	105560000	107160000
3	107200000	108600000
3	109240000	112080000
3	112120000	112520000
3	112560000	113040000
3	113040000	113640000
3	114280000	115200000
3	115200000	115840000
3	115920000	116480000
3	116760000	119120000
3	119120000	120240000
3	120560000	121440000
3	121520000	122360000
3	122400000	123280000
3	123600000	124720000
3	124760000	125680000
3	125920000	127560000
3	127600000	128080000
3	128080000	128640000
3	128640000	129280000
3	129360000	130120000
3	130120000	132400000
3	132400000	132720000
3	132720000	133720000
3	133920000	134560000
3	134560000	135880000
3	136080000	137040000
3	137040000	138000000
3	138160000	138920000
3	139040000	139400000
3	139400000	141200000
3	141200000	142440000
3	142560000	143720000
3	143800000	145800000
3	146040000	146600000
3	146640000	148920000
3	148960000	149800000
3	149840000	150560000
3	150640000	151920000
3	152000000	152600000
3	152800000	154280000
3	154320000	155760000
3	155960000	157160000
3	157160000	157520000
3	157560000	158800000
3	158840000	160560000
3	160600000	161440000
3	161520000	165120000
3	165920000	167680000
3	167880000	168840000
3	168960000	169800000
3	170160000	170880000
3	170880000	171600000
3	171640000	172800000
3	172800000	176480000
3	176880000	178400000
3	178440000	179000000
3	179000000	179600000
3	179760000	180600000
3	180680000	182720000
3	183000000	183400000
3	183440000	183800000
3	183880000	184320000
3	184360000	184800000
3	184800000	185560000
3	185600000	185920000
3	185960000	186560000
3	186840000	187720000
3	187720000	189200000
3	189240000	189920000
3	189920000	190720000
3	190760000	191440000
3	191440000	192480000
3	192560000	193600000
3	193640000	194320000
3	194360000	194640000
3	194640000	195960000
3	196000000	196520000
3	196960000	198295559
4	0	2960000
4	3080000	3520000
4	3600000	6560000
4	6640000	7080000
4	7120000	8640000
4	8640000	12640000
4	12760000	13560000
4	13560000	15200000
4	15240000	15480000
4	16000000	17520000
4	17640000	18640000
4	18640000	20720000
4	20760000	22760000
4	22960000	24480000
4	24480000	25400000
4	25880000	27040000
4	27040000	30560000
4	30680000	37400000
4	37520000	38760000
4	38880000	40000000
4	40040000	41280000
4	41280000	41920000
4	42920000	44720000
4	44760000	46760000
4	46840000	49080000
4	51800000	54280000
4	54280000	54960000
4	55000000	56360000
4	56520000	57160000
4	57160000	62080000
4	64680000	67400000
4	67480000	69240000
4	70560000	71760000
4	72280000	73040000
4	73040000	74160000
4	74360000	75880000
4	75960000	77240000
4	77360000	78920000
4	78960000	80320000
4	80360000	82320000
4	82320000	83360000
4	83480000	84520000
4	84680000	85000000
4	85040000	86080000
4	86480000	87240000
4	87600000	88520000
4	88520000	89160000
4	89200000	89960000
4	90160000	92400000
4	92680000	94200000
4	94200000	95160000
4	95160000	98040000
4	98080000	99080000
4	99120000	99480000
4	99520000	102360000
4	102400000	103200000
4	103240000	105520000
4	106240000	107680000
4	107960000	108600000
4	108640000	110000000
4	110000000	110560000
4	110560000	112080000
4	112080000	112800000
4	113000000	114800000
4	114880000	116880000
4	117080000	118280000
4	118280000	119320000
4	119480000	120080000
4	120080000	121640000
4	121880000	122960000
4	122960000	124280000
4	124320000	125280000
4	125320000	127880000
4	128040000	129120000
4	129360000	132960000
4	133080000	136920000
4	137040000	139000000
4	139000000	140360000
4	140400000	141160000
4	141160000	143560000
4	144040000	145080000
4	145160000	147000000
4	147120000	147920000
4	147920000	149920000
4	149960000	151040000
4	151080000	152760000
4	152800000	153120000
4	153120000	153760000
4	153800000	155320000
4	155360000	155800000
4	155960000	158680000
4	158680000	159480000
4	159480000	162360000
4	163040000	164800000
4	165120000	168120000
4	168160000	168960000
4	169000000	169760000
4	169760000	172840000
4	173000000	173280000
4	173480000	174360000
4	174360000	175920000
4	176000000	177520000
4	177560000	180440000
4	180640000	183440000
4	183480000	184600000
4	185160000	186200000
4	186280000	190040000
5	280000	1600000
5	1680000	7840000
5	7840000	10440000
5	10440000	13960000
5	13960000	14680000
5	14680000	15040000
5	15040000	16160000
5	16440000	17200000
5	17200000	18400000
5	18480000	21280000
5	21520000	28360000
5	30360000	31560000
5	31560000	32080000
5	32120000	33440000
5	33440000	34120000
5	34480000	34920000
5	34920000	35960000
5	36120000	36840000
5	37360000	38320000
5	38400000	38920000
5	38920000	39560000
5	39560000	40840000
5	40880000	42840000
5	43600000	44840000
5	44920000	46440000
5	50120000	52640000
5	52800000	54240000
5	54240000	55200000
5	55320000	56920000
5	57280000	58480000
5	58560000	59200000
5	59400000	60600000
5	60920000	62240000
5	62400000	64600000
5	64640000	65600000
5	65600000	66200000
5	66200000	67160000
5	67240000	69600000
5	71360000	72320000
5	72320000	72920000
5	72920000	73560000
5	73560000	73800000
5	73880000	74680000
5	74760000	76560000
5	76560000	78280000
5	78280000	79000000
5	79040000	80440000
5	80640000	81280000
5	81280000	82280000
5	82280000	83640000
5	83680000	86800000
5	87040000	87440000
5	87600000	88680000
5	88680000	90800000
5	90840000	91440000
5	91560000	95440000
5	95480000	96360000
5	96360000	96720000
5	96760000	97160000
5	97200000	99080000
5	99080000	102080000
5	102480000	103160000
5	103240000	103520000
5	103560000	108400000
5	108400000	109480000
5	109520000	110720000
5	110720000	112200000
5	112520000	113600000
5	113600000	115240000
5	115280000	115640000
5	115640000	116080000
5	116080000	118960000
5	118960000	119440000
5	119440000	121960000
5	121960000	122480000
5	122480000	123600000
5	123640000	126600000
5	126640000	127520000
5	127520000	128200000
5	128200000	128880000
5	129240000	129800000
5	129880000	131160000
5	131160000	132040000
5	132200000	133040000
5	133080000	134000000
5	134040000	134880000
5	134880000	135440000
5	135440000	136200000
5	136200000	138160000
5	138440000	139400000
5	139800000	140720000
5	140720000	141640000
5	141640000	141960000
5	141960000	142560000
5	142720000	144200000
5	144200000	146160000
5	146480000	148720000
5	148720000	149280000
5	149320000	149560000
5	149600000	150000000
5	150000000	151160000
5	151240000	151800000
5	151800000	154840000
5	154960000	157160000
5	157240000	157760000
5	157760000	159160000
5	159160000	160440000
5	160440000	163440000
5	163440000	167480000
5	167560000	168240000
5	168280000	168560000
5	168600000	169560000
5	169560000	170640000
5	170800000	171360000
5	171400000	171920000
5	172080000	172360000
5	172440000	172960000
5	172960000	173600000
5	173600000	174000000
5	174000000	174880000
5	174960000	176360000
5	176400000	177520000
5	177920000	181320000
6	80000	1480000
6	1520000	3000000
6	3080000	4040000
6	4040000	5040000
6	5120000	5400000
6	5400000	6640000
6	6640000	7280000
6	7280000	7640000
6	7640000	8080000
6	8080000	10680000
6	10800000	11520000
6	11560000	12640000
6	13320000	13600000
6	13760000	15680000
6	15680000	16240000
6	16280000	16760000
6	16760000	17120000
6	17120000	17840000
6	17840000	18280000
6	18520000	20080000
6	20240000	21560000
6	21560000	24400000
6	24400000	26000000
6	26000000	26600000
6	26960000	27920000
6	27920000	30200000
6	30480000	31480000
6	31640000	31960000
6	32200000	33280000
6	33560000	34160000
6	34160000	35320000
6	35480000	37240000
6	37280000	38720000
6	38720000	41720000
6	41720000	42040000
6	42040000	43520000
6	43640000	44360000
6	44400000	46680000
6	47080000	47360000
6	47400000	49560000
6	49880000	52040000
6	52280000	52680000
6	52800000	55280000
6	55280000	56320000
6	56320000	56600000
6	56640000	58480000
6	60200000	63840000
6	63920000	68440000
6	68800000	70160000
6	70200000	72120000
6	72160000	73400000
6	73440000	75760000
6	75840000	79840000
6	79880000	82240000
6	82240000	83600000
6	83640000	84240000
6	84280000	85680000
6	85680000	86920000
6	87040000	88960000
6	88960000	89640000
6	89840000	90600000
6	90960000	95040000
6	95360000	96480000
6	96560000	99280000
6	99440000	100680000
6	100920000	104600000
6	104840000	106360000
6	106360000	107000000
6	107080000	107880000
6	107960000	108520000
6	108520000	109440000
6	109480000	110480000
6	110480000	111000000
6	111240000	112040000
6	112080000	113960000
6	114000000	116000000
6	116160000	116760000
6	117240000	117680000
6	118240000	118920000
6	118960000	121040000
6	121400000	122360000
6	122480000	124800000
6	124840000	126000000
6	126000000	127240000
6	127280000	127560000
6	127640000	128760000
6	128800000	129480000
6	129480000	130040000
6	130040000	130840000
6	130880000	131640000
6	131640000	132800000
6	132800000	133560000
6	133560000	134120000
6	134120000	135000000
6	135040000	135440000
6	135440000	136800000
6	136840000	137680000
6	137680000	138760000
6	138800000	142120000
6	142160000	142440000
6	142440000	143480000
6	143560000	144040000
6	144080000	144520000
6	144560000	145920000
6	145920000	146800000
6	146800000	147360000
6	147400000	148520000
6	148520000	149000000
6	149040000	149920000
6	150040000	150800000
6	150840000	151400000
6	151440000	153000000
6	153000000	154120000
6	154120000	154640000
6	154680000	155240000
6	155280000	157280000
6	157320000	158160000
6	158200000	159000000
6	159120000	159680000
6	159680000	160080000
6	160200000	160520000
6	160640000	161360000
6	161400000	165200000
6	165360000	166160000
6	166240000	168880000
6	168880000	170640000
7	0	1440000
7	1520000	2400000
7	2440000	5160000
7	5280000	5760000
7	5960000	6480000
7	6520000	8280000
7	8320000	11360000
7	11720000	12400000
7	12520000	13280000
7	13280000	14720000
7	15240000	16600000
7	16640000	17680000
7	17680000	18320000
7	18360000	18600000
7	18680000	19680000
7	19720000	20640000
7	20680000	22080000
7	22080000	22520000
7	22520000	23080000
7	23280000	23560000
7	23560000	25160000
7	25160000	27160000
7	27160000	28200000
7	28280000	29480000
7	29720000	30440000
7	30640000	31160000
7	31760000	32480000
7	32720000	35080000
7	35640000	35920000
7	35960000	36440000
7	36440000	37240000
7	38080000	39560000
7	39560000	41960000
7	41960000	42880000
7	42920000	43960000
7	44040000	45120000
7	45160000	47280000
7	47360000	48120000
7	48160000	50120000
7	50440000	51360000
7	51440000	54720000
7	54720000	58040000
7	61720000	65520000
7	65720000	67000000
7	67320000	72800000
7	73280000	74760000
7	75400000	76360000
7	76640000	79240000
7	79240000	80080000
7	80080000	80680000
7	80680000	81480000
7	81480000	82760000
7	83160000	85880000
7	85920000	88120000
7	88240000	90120000
7	90120000	91040000
7	91080000	92480000
7	92560000	93080000
7	93240000	95720000
7	95840000	98880000
7	98880000	99440000
7	99640000	100120000
7	100880000	102480000
7	102680000	104920000
7	104920000	105520000
7	105520000	106040000
7	106160000	107160000
7	107200000	108160000
7	108160000	108560000
7	108560000	111720000
7	111720000	112480000
7	112520000	113720000
7	113760000	116120000
7	116160000	116880000
7	116920000	117400000
7	117400000	118240000
7	118280000	120520000
7	120720000	123440000
7	123480000	124960000
7	125200000	127560000
7	127560000	128360000
7	128480000	130040000
7	130040000	130840000
7	130880000	131040000
7	131080000	131520000
7	131680000	134400000
7	134600000	135240000
7	135280000	135520000
7	135640000	137640000
7	137640000	139120000
7	139360000	140680000
7	140680000	141800000
7	142320000	143560000
7	144400000	148480000
7	148640000	149080000
7	149280000	152840000
7	152840000	154720000
7	154880000	157400000
7	157440000	159345973
8	120000	2080000
8	2320000	6400000
8	6400000	7160000
8	8200000	8680000
8	8680000	9000000
8	9040000	9840000
8	9840000	10480000
8	10520000	12040000
8	12600000	13680000
8	13720000	17280000
8	17320000	17920000
8	17920000	18800000
8	18880000	19360000
8	19360000	20160000
8	20200000	22040000
8	22080000	23440000
8	23440000	24240000
8	24440000	25080000
8	25160000	27280000
8	27840000	28600000
8	28760000	30160000
8	30160000	30640000
8	30800000	31200000
8	31200000	32560000
8	32560000	33600000
8	33680000	36800000
8	36800000	37760000
8	38120000	38760000
8	38800000	39120000
8	39120000	41560000
8	41640000	42160000
8	42160000	42400000
8	42400000	44000000
8	45960000	47760000
8	47920000	48960000
8	48960000	51680000
8	52040000	52480000
8	52520000	54040000
8	54160000	56040000
8	56200000	57200000
8	57400000	58400000
8	58560000	60320000
8	60440000	61120000
8	61480000	63120000
8	63400000	64400000
8	64560000	65600000
8	65640000	66440000
8	66440000	67800000
8	68480000	69680000
8	69880000	70680000
8	70720000	71800000
8	71800000	72280000
8	73240000	74960000
8	75360000	78360000
8	78480000	79640000
8	79640000	81720000
8	81920000	84560000
8	84600000	85080000
8	86600000	89680000
8	89720000	90000000
8	90040000	90960000
8	91200000	93640000
8	93680000	93960000
8	93960000	94560000
8	94600000	96240000
8	96240000	97640000
8	97720000	98120000
8	98120000	100120000
8	100120000	100560000
8	100560000	101320000
8	101320000	102240000
8	102240000	102840000
8	103080000	103560000
8	103720000	104440000
8	104480000	105800000
8	105880000	106680000
8	106680000	107800000
8	107800000	108760000
8	108840000	109360000
8	109720000	113440000
8	115040000	117320000
8	117320000	119800000
8	119840000	120920000
8	120920000	121640000
8	121640000	122680000
8	122680000	123240000
8	123400000	124480000
8	124520000	125040000
8	125080000	125720000
8	125720000	126800000
8	126800000	127720000
8	127720000	129800000
8	130080000	130720000
8	130720000	132640000
8	132760000	133480000
8	133480000	134880000
8	134920000	138480000
8	138720000	140640000
8	140640000	141400000
8	141440000	143280000
8	143560000	145138636
9	40000	2840000
9	2880000	4680000
9	4720000	5760000
9	5840000	6720000
9	6800000	9920000
9	10120000	12440000
9	12600000	15120000
9	15160000	17480000
9	17520000	19480000
9	19480000	21200000
9	21320000	21800000
9	21800000	22240000
9	22480000	26680000
9	26720000	32360000
9	32360000	33000000
9	33000000	33240000
9	33560000	35600000
9	35760000	36560000
9	36600000	37440000
9	37480000	39120000
9	68320000	70640000
9	70640000	73200000
9	73240000	74720000
9	75240000	77160000
9	77160000	78240000
9	78280000	80160000
9	80240000	83600000
9	83920000	84320000
9	84360000	85800000
9	86280000	87680000
9	88080000	88560000
9	88600000	89320000
9	89360000	90880000
9	90880000	92120000
9	92160000	92800000
9	92880000	93560000
9	94000000	94240000
9	94440000	95120000
9	95160000	97640000
9	97640000	98800000
9	98800000	100600000
9	100640000	101600000
9	101600000	104760000
9	104760000	105560000
9	105760000	107200000
9	107400000	108880000
9	108920000	109400000
9	109520000	110160000
9	110240000	111480000
9	111680000	112080000
9	112080000	113120000
9	113280000	113680000
9	113680000	114320000
9	114320000	115560000
9	115560000	116680000
9	116680000	120560000
9	120600000	121480000
9	121480000	122080000
9	122080000	122400000
9	122480000	122840000
9	123080000	123360000
9	123400000	124400000
9	124440000	124800000
9	124840000	125160000
9	125400000	126800000
9	126880000	128120000
9	128320000	129800000
9	129880000	130680000
9	130680000	131360000
9	131520000	132360000
9	132360000	133000000
9	133320000	134040000
9	134160000	134760000
9	134840000	137480000
9	137600000	138200000
10	40000	1080000
10	1080000	3080000
10	3080000	4840000
10	4840000	5920000
10	6400000	7480000
10	7720000	9320000
10	9320000	11800000
10	12120000	13200000
10	13360000	14920000
10	15400000	16760000
10	16800000	17280000
10	17840000	18240000
10	18680000	20960000
10	21040000	23120000
10	23160000	24560000
10	24560000	26600000
10	26680000	28520000
10	28520000	29440000
10	29480000	30600000
10	30640000	32040000
10	32400000	35080000
10	35080000	35560000
10	35560000	36920000
10	37200000	39560000
10	41680000	46120000
10	46960000	47480000
10	48160000	49880000
10	50120000	50680000
10	50760000	52800000
10	52800000	58120000
10	58160000	60080000
10	60080000	60720000
10	60760000	63160000
10	63160000	63840000
10	63880000	67840000
10	67840000	68360000
10	68360000	68960000
10	69240000	69960000
10	70160000	72360000
10	72360000	73680000
10	73800000	74120000
10	74120000	75280000
10	75280000	77120000
10	77160000	77800000
10	77800000	79520000
10	79520000	83960000
10	84120000	86400000
10	86680000	86960000
10	87320000	89240000
10	89240000	90880000
10	90880000	91280000
10	91320000	91960000
10	92000000	92480000
10	92520000	93520000
10	93720000	94560000
10	94560000	96360000
10	96560000	97640000
10	97760000	98440000
10	98440000	99640000
10	99720000	100280000
10	100280000	101000000
10	101040000	101800000
10	101800000	102120000
10	102120000	102640000
10	102680000	103560000
10	103600000	104360000
10	104360000	109840000
10	109880000	110600000
10	110600000	111040000
10	111040000	112120000
10	112440000	113600000
10	113680000	114120000
10	114160000	115160000
10	115280000	116520000
10	116560000	117200000
10	117400000	119040000
10	119080000	119960000
10	119960000	121920000
10	122000000	124440000
10	124480000	125720000
10	125800000	128040000
10	128160000	130200000
10	130200000	133797422
11	80000	1560000
11	1600000	3400000
11	3600000	4120000
11	4120000	5920000
11	6360000	6680000
11	6720000	8600000
11	8600000	9160000
11	9160000	10760000
11	10760000	11800000
11	12040000	12280000
11	12280000	12960000
11	12960000	13480000
11	13480000	14280000
11	14280000	14520000
11	14520000	16800000
11	17560000	18840000
11	19000000	20440000
11	20640000	22800000
11	22800000	26600000
11	26720000	27160000
11	27160000	27520000
11	27520000	29400000
11	29440000	30960000
11	31160000	32840000
11	32880000	33760000
11	34120000	34920000
11	34920000	35440000
11	35480000	36520000
11	36560000	43320000
11	43320000	45800000
11	45840000	46320000
11	46360000	46600000
11	46680000	48160000
11	48200000	50840000
11	54520000	57240000
11	57320000	61200000
11	61280000	63960000
11	64000000	64240000
11	64360000	64800000
11	64840000	65520000
11	65640000	67400000
11	67960000	69680000
11	69680000	70400000
11	70440000	71600000
11	71840000	72440000
11	72720000	73320000
11	73360000	73680000
11	73960000	75280000
11	75400000	76720000
11	77120000	77640000
11	78080000	78560000
11	78600000	79520000
11	79560000	82440000
11	82640000	83840000
11	83840000	84600000
11	84720000	85600000
11	85600000	86320000
11	86320000	86920000
11	86920000	87320000
11	87320000	89680000
11	90080000	92920000
11	92920000	93680000
11	93760000	94520000
11	94520000	94920000
11	95000000	95760000
11	95800000	96440000
11	96440000	99000000
11	99120000	100560000
11	100600000	101360000
11	101400000	102040000
11	102040000	102680000
11	102800000	103080000
11	103080000	103600000
11	103600000	106080000
11	106080000	107320000
11	107520000	107920000
11	108000000	108680000
11	108680000	109920000
11	110200000	111440000
11	111560000	112080000
11	112280000	113800000
11	113880000	116720000
11	116760000	117200000
11	117400000	118560000
11	118680000	119000000
11	119080000	119320000
11	119360000	120120000
11	120320000	120960000
11	121200000	121600000
11	121600000	122600000
11	122600000	123080000
11	123080000	123560000
11	123720000	124600000
11	124640000	125880000
11	125880000	126280000
11	126280000	127000000
11	128000000	129840000
11	129880000	130160000
11	130200000	130920000
11	130920000	135086622
12	0	1640000
12	1640000	2840000
12	3040000	4280000
12	4800000	6840000
12	7200000	8200000
12	8440000	10760000
12	10760000	11520000
12	11520000	12040000
12	12080000	12760000
12	12920000	13240000
12	13240000	15880000
12	16040000	18120000
12	18120000	19360000
12	19720000	20680000
12	21520000	22440000
12	22680000	24840000
12	24960000	26040000
12	26080000	27680000
12	27720000	29080000
12	29080000	31240000
12	31280000	32360000
12	32360000	32760000
12	32760000	34720000
12	37240000	42080000
12	42080000	43920000
12	43960000	45080000
12	45120000	45760000
12	46000000	48800000
12	49080000	49600000
12	49640000	50760000
12	50760000	51400000
12	51400000	51880000
12	52040000	53000000
12	53040000	53520000
12	53520000	54480000
12	54600000	55720000
12	55720000	57720000
12	57760000	59200000
12	59360000	62200000
12	62240000	63560000
12	63800000	64400000
12	64400000	64760000
12	64760000	66720000
12	66920000	68800000
12	68840000	69160000
12	69320000	70800000
12	71760000	74600000
12	74640000	75320000
12	75320000	76040000
12	76040000	76600000
12	76600000	77040000
12	77040000	77960000
12	77960000	79400000
12	79400000	80280000
12	80400000	81320000
12	81520000	84840000
12	85320000	85880000
12	85880000	88040000
12	88040000	89000000
12	89000000	89520000
12	89520000	90960000
12	90960000	91360000
12	91360000	92720000
12	92760000	93440000
12	93440000	94120000
12	94120000	94520000
12	95040000	95560000
12	95560000	95880000
12	96040000	96520000
12	96560000	99000000
12	100040000	100600000
12	100760000	101400000
12	101400000	103760000
12	103760000	105120000
12	105120000	105400000
12	105400000	106320000
12	106360000	107000000
12	107080000	107640000
12	107920000	108520000
12	108520000	109800000
12	109960000	110400000
12	110440000	110640000
12	110920000	111320000
12	111680000	112440000
12	112520000	114560000
12	114600000	115960000
12	115960000	117160000
12	117200000	118400000
12	118400000	120080000
12	120320000	121280000
12	121840000	123640000
12	123680000	125000000
12	125000000	127960000
12	128600000	132840000
12	132880000	133275309
13	18640000	21480000
13	21480000	23320000
13	23320000	24320000
13	24560000	26920000
13	26920000	27360000
13	27360000	28000000
13	28120000	29400000
13	29440000	30120000
13	30120000	31160000
13	31160000	31840000
13	31840000	33760000
13	33800000	35960000
13	36280000	36800000
13	37000000	38920000
13	39000000	40800000
13	40920000	42280000
13	42280000	43880000
13	43880000	44480000
13	44480000	45360000
13	45520000	46160000
13	46440000	48080000
13	48080000	48760000
13	49280000	49640000
13	49640000	51120000
13	51120000	52480000
13	52680000	59320000
13	59360000	61920000
13	62280000	64360000
13	64440000	67440000
13	71200000	72680000
13	72720000	73720000
13	73720000	75520000
13	75560000	77040000
13	77040000	79280000
13	79400000	80520000
13	81080000	84840000
13	84880000	85880000
13	86040000	87320000
13	87840000	91040000
13	92040000	94560000
13	95160000	95880000
13	96040000	96920000
13	97000000	97800000
13	97800000	99120000
13	99200000	99440000
13	99600000	100560000
13	100640000	102880000
13	102880000	107160000
13	107200000	108240000
13	108320000	108920000
13	108920000	110200000
13	110200000	110480000
13	110720000	112920000
13	112960000	113600000
13	113840000	114364328
14	18640000	24440000
14	24520000	25160000
14	25200000	28640000
14	28680000	29520000
14	29520000	30560000
14	30640000	31360000
14	31440000	32560000
14	32560000	34520000
14	34560000	35840000
14	35840000	37160000
14	37240000	39040000
14	39120000	39440000
14	39440000	41520000
14	42040000	44880000
14	44880000	45280000
14	45320000	49600000
14	49600000	50880000
14	50920000	52160000
14	52720000	54480000
14	54480000	55000000
14	55040000	56520000
14	56520000	58200000
14	58240000	59520000
14	59600000	61320000
14	61320000	61840000
14	61880000	63600000
14	63800000	65000000
14	65120000	67360000
14	67360000	69760000
14	69760000	72480000
14	72480000	73000000
14	73120000	74080000
14	74080000	74840000
14	74920000	75120000
14	75120000	75320000
14	75320000	75560000
14	75680000	76400000
14	76880000	77760000
14	77800000	78840000
14	78880000	81520000
14	81560000	85640000
14	86080000	87920000
14	87920000	88440000
14	88560000	90240000
14	90280000	91320000
14	91440000	92040000
14	92080000	92840000
14	92920000	95360000
14	95440000	96520000
14	96920000	99440000
14	99480000	99920000
14	99960000	100200000
14	100320000	101720000
14	101760000	102360000
14	102360000	103040000
14	103080000	103560000
14	103560000	107043718
15	22600000	28320000
15	28760000	29560000
15	29680000	30120000
15	30600000	32160000
15	32600000	33160000
15	33160000	34360000
15	34560000	34960000
15	35000000	37920000
15	37960000	38440000
15	38440000	38680000
15	38680000	40440000
15	40560000	42480000
15	42680000	43680000
15	43800000	44560000
15	44640000	47080000
15	47160000	48320000
15	48320000	49160000
15	49160000	50360000
15	50480000	50920000
15	51160000	51520000
15	51960000	52760000
15	52800000	55160000
15	55200000	57560000
15	58200000	58960000
15	58960000	59680000
15	59680000	61840000
15	62320000	62760000
15	62760000	63080000
15	63160000	64160000
15	64160000	65160000
15	65320000	66360000
15	66560000	68240000
15	68240000	68920000
15	69000000	69440000
15	69480000	70640000
15	70640000	72240000
15	72240000	72600000
15	72640000	73920000
15	74120000	74360000
15	74360000	75280000
15	75320000	76920000
15	76920000	77880000
15	77920000	80200000
15	80400000	81000000
15	81000000	82320000
15	82520000	84160000
15	84520000	85720000
15	85840000	88480000
15	88640000	88880000
15	88880000	89320000
15	89600000	90120000
15	90280000	90960000
15	90960000	92720000
15	92800000	93040000
15	93040000	94160000
15	94640000	98400000
15	98440000	99240000
15	99240000	99800000
15	99840000	100600000
15	100600000	101991189
16	680000	2000000
16	2240000	2560000
16	3040000	5080000
16	5080000	8400000
16	8520000	10920000
16	10920000	11880000
16	12080000	13880000
16	13920000	14680000
16	15400000	16240000
16	16760000	18160000
16	18760000	19880000
16	19920000	20560000
16	20760000	21400000
16	21560000	22440000
16	22600000	23440000
16	23720000	24520000
16	24520000	25160000
16	25240000	27480000
16	27600000	28640000
16	28800000	30040000
16	30320000	30960000
16	30960000	31960000
16	34000000	36280000
16	46400000	48640000
16	48640000	49440000
16	50000000	52120000
16	52160000	53360000
16	53520000	55880000
16	55920000	56360000
16	56400000	57520000
16	57560000	58680000
16	58680000	63120000
16	63320000	65000000
16	65120000	66880000
16	66880000	67480000
16	67480000	68240000
16	68240000	69320000
16	69360000	69960000
16	70360000	74320000
16	74400000	75160000
16	75160000	75440000
16	75640000	77200000
16	77200000	78040000
16	78080000	80960000
16	81000000	81760000
16	81800000	84480000
16	84480000	85080000
16	85080000	85640000
16	85720000	86520000
16	86560000	87800000
16	87920000	88560000
16	88880000	89200000
16	89280000	90120000
17	80000	1000000
17	1200000	2040000
17	2040000	2720000
17	2720000	3640000
17	3680000	4920000
17	5200000	7200000
17	7280000	8080000
17	8400000	10600000
17	10880000	12000000
17	12000000	13000000
17	13040000	15560000
17	16000000	16360000
17	16840000	19040000
17	19200000	22760000
17	26600000	27640000
17	27760000	28440000
17	28680000	29120000
17	29120000	30680000
17	30840000	31400000
17	31520000	32360000
17	32440000	33720000
17	34160000	36240000
17	36520000	37360000
17	37400000	37920000
17	38760000	41720000
17	41920000	43000000
17	43360000	44160000
17	44360000	45120000
17	45200000	45440000
17	45600000	45920000
17	46000000	46280000
17	46680000	47480000
17	47800000	48920000
17	49280000	50360000
17	50480000	51160000
17	51280000	54880000
17	54960000	57000000
17	57080000	59080000
17	59240000	59600000
17	59600000	59880000
17	60040000	62440000
17	62480000	63840000
17	63840000	64800000
17	64920000	66200000
17	66200000	67360000
17	67360000	67720000
17	68040000	70640000
17	70640000	72560000
17	72720000	73400000
17	73440000	74920000
17	74960000	75760000
17	75880000	76720000
17	76720000	78200000
17	78480000	78840000
17	79000000	80000000
17	80120000	81720000
17	82240000	82640000
17	82760000	83257441
18	40000	2560000
18	2600000	3240000
18	3240000	4080000
18	4080000	6960000
18	7200000	8600000
18	8600000	9560000
18	9560000	9920000
18	9960000	10520000
18	10560000	12320000
18	12360000	12680000
18	12720000	13000000
18	13160000	15440000
18	20920000	22800000
18	23040000	23480000
18	23480000	24160000
18	24440000	26120000
18	26240000	31440000
18	32040000	32560000
18	33120000	34840000
18	34880000	35200000
18	35400000	35960000
18	36000000	36880000
18	37560000	42080000
18	42080000	43480000
18	43560000	45640000
18	45640000	46120000
18	46120000	46720000
18	47000000	47760000
18	48480000	49480000
18	49480000	50400000
18	50560000	54120000
18	54400000	56680000
18	56720000	57600000
18	57600000	58480000
18	58520000	59400000
18	59440000	59840000
18	59960000	60600000
18	60680000	62160000
18	62320000	64000000
18	64040000	67080000
18	67080000	68760000
18	68840000	70520000
18	70520000	72600000
18	72680000	74360000
18	74560000	76800000
18	76840000	79360000
18	79360000	80373285
19	240000	4240000
19	4760000	5680000
19	5760000	6360000
19	6440000	8280000
19	8320000	8560000
19	8760000	9840000
19	9920000	12880000
19	12960000	13840000
19	14520000	16480000
19	17400000	17920000
19	18440000	18920000
19	19520000	24440000
19	27240000	29560000
19	29720000	32640000
19	33160000	35640000
19	36120000	38400000
19	38960000	39400000
19	39480000	40240000
19	40880000	41880000
19	42080000	42280000
19	43680000	44880000
19	45840000	46600000
19	46720000	47240000
19	47440000	47720000
19	47960000	48320000
19	48640000	49480000
19	49880000	53680000
19	54480000	55680000
19	55680000	58617616
20	40000	1480000
20	1760000	3000000
20	3200000	5160000
20	5200000	6040000
20	6080000	7920000
20	7960000	8760000
20	8760000	9400000
20	9640000	10440000
20	10440000	11560000
20	11600000	13800000
20	13880000	16760000
20	16800000	17480000
20	17480000	18040000
20	18520000	20040000
20	20080000	20720000
20	20800000	21640000
20	22320000	23640000
20	23800000	26400000
20	28720000	33360000
20	33440000	34160000
20	34320000	34800000
20	34800000	35520000
20	35720000	35960000
20	35960000	36440000
20	36560000	36920000
20	37080000	38440000
20	38600000	40960000
20	40960000	41120000
20	41120000	41680000
20	41720000	43440000
20	43440000	44640000
20	44880000	45800000
20	46000000	46680000
20	46680000	47160000
20	47200000	47640000
20	47680000	48960000
20	49040000	49920000
20	50120000	50760000
20	50960000	51360000
20	51360000	52120000
20	52200000	53560000
20	53560000	54680000
20	54720000	56360000
20	56360000	57080000
20	57360000	58200000
20	58200000	59520000
20	59600000	62160000
20	62520000	63480000
20	63520000	64444167
21	13200000	15520000
21	15600000	15880000
21	15880000	17960000
21	18000000	20040000
21	20920000	22000000
21	24000000	25400000
21	25880000	26720000
21	26720000	27720000
21	28040000	29000000
21	29000000	29400000
21	29400000	31640000
21	31640000	32600000
21	32800000	33480000
21	33520000	34360000
21	34480000	36280000
21	36400000	37000000
21	37160000	37560000
21	37640000	38400000
21	38720000	39440000
21	39480000	42880000
21	43160000	43720000
21	43800000	44120000
21	44320000	46709983
22	16000000	17520000
22	17560000	18160000
22	18960000	19960000
22	20360000	21120000
22	21680000	21920000
22	21960000	23320000
22	23960000	24600000
22	24760000	26360000
22	26480000	27880000
22	27880000	29280000
22	29320000	31400000
22	31640000	33000000
22	33040000	35280000
22	35320000	36480000
22	36520000	37600000
22	37960000	38680000
22	38760000	40400000
22	40400000	41520000
22	41680000	41960000
22	41960000	42520000
22	42600000	43160000
22	43160000	43880000
22	43960000	44680000
22	44760000	45560000
22	45560000	46560000
22	46760000	50818468
23	240000	2600000
23	3000000	3840000
23	3920000	8680000
23	8720000	10120000
23	10160000	11120000
23	11120000	11760000
23	11800000	12800000
23	12920000	14040000
23	14040000	15320000
23	15680000	16800000
23	16800000	18200000
23	18360000	19360000
23	19520000	20120000
23	20200000	21760000
23	22000000	25160000
23	25280000	27320000
23	27520000	30560000
23	30800000	31680000
23	32400000	34080000
23	34480000	36960000
23	37280000	38360000
23	38640000	40560000
23	40560000	41280000
23	41760000	43760000
23	43920000	45120000
23	45280000	46440000
23	46560000	47160000
23	47160000	48080000
23	49600000	52680000
23	52960000	58560000
23	62480000	65360000
23	65560000	68000000
23	68160000	71680000
23	71840000	72760000
23	72960000	75560000
23	76320000	78120000
23	78400000	90120000
23	92120000	100400000
23	100640000	102040000
23	102480000	107960000
23	108160000	110440000
23	110440000	115720000
23	115880000	118280000
23	118440000	119960000
23	121000000	124120000
23	124360000	129320000
23	129400000	130240000
23	130320000	130960000
23	131160000	134360000
23	134400000	135120000
23	135920000	136920000
23	137160000	140720000
23	140760000	149520000
23	149920000	150760000
23	151080000	152680000
23	152920000	154560000
23	154640000	154880000
23	154880000	156040000