Эдвард — нарықтағы ең қауіпсіз сейфтерді шығаратын Enigma компаниясының негізін қалаушы әрі басшысы. Enigma сейфтері 5 таңбалы коды бар құпия құлыппен қорғалған. Құлып бес дөңгелектен және «ашу» батырмасынан тұрады. Әр дөңгелекте 0-ден 9-ға дейінгі барлық цифрлар (осы ретпен) орналасқан; 9 цифрынан кейін қайтадан 0 цифры пайда болады.

Бір амал ретінде кез келген дөңгелекті кез келген бағытта бір орынға бұру анықталады, мысалы 9 цифрын 8 немесе 0-ге өзгерту. Екі кодтың арасындағы арақашықтық деп енгізілген бір кодты екіншісіне ауыстыру үшін қажет ең аз мүмкін амалдар санын айтады. Мысалы, 38911 мен 68000 арасындағы арақашықтық $3 + 0 + 1 + 1 + 1 = 6$ тең.

Сейф өндірушілері ең жиі қолданылатын кодтардың статистикасын жүргізеді — сізге ең танымалынан ең аз танымалына қарай реттелген осындай $n$ код беріледі. Enigma өзінің икемділігімен мақтанады — әр клиент ең танымал $n$ кодтың алғашқы қаншауынан аулақ болғысы келетінін таңдай алады. Содан кейін Эдвард ең танымал кодтар тізбегінің таңдалған префиксіндегі кодтарға дейінгі ең кіші арақашықтықты барынша арттыратын кодты таңдайды.

1-ден $n$-ге дейінгі әрбір $k$ үшін сіздің міндетіңіз — қандай да бір кодтан ең танымал $k$ кодтың ішіндегі ең жақынына дейінгі ең үлкен мүмкін арақашықтықты табу және осындай арақашықтыққа қол жеткізетін қанша код бар екенін санау.

Кіріс деректер

Бірінші жолда танымал кодтардың санын білдіретін бүтін $n$ ($1 \le n \le 99\,999$) саны берілген.

Келесі $n$ жолдың әрқайсысында алдында нөлдері болуы мүмкін 0–9 аралығындағы 5 цифрдан тұратын жол берілген. Бұл ең танымалынан ең аз танымалына қарай реттелген танымал кодтар. Барлық кодтар қос-қостан әртүрлі.

Шығыс деректер

$n$ жол шығарыңыз; $k$-шы жолда бос орынмен бөлінген екі бүтін сан болуы тиіс — ең танымал $k$ кодтың ішіндегі ең жақын кодқа дейінгі ең үлкен мүмкін арақашықтық және осындай арақашықтығы бар кодтардың саны.

Мысалдар

Кіріс деректер 1

3
00000
00001
12345

Шығыс деректер 1

25 1
24 2
17 270

Кіріс деректер 2

3
12345
23456
67890

Шығыс деректер 2

25 1
22 20
12 15270

Ескертпе

$k = 1$ үшін 00000 кодынан ең үлкен мүмкін арақашықтық 25-ке тең, оған тек 55555 коды ғана жетеді.

$k = 2$ үшін 00000 және 00001 кодтарының жақынырағына дейінгі ең үлкен мүмкін арақашықтық 24-ке тең, оған екі код жетеді: 55555 және 55556. Біріншісі 00001 кодынан 24 қашықтықта, ал екіншісі 00000 кодынан 24 қашықтықта орналасқан.

$k = 3$ үшін 00000, 00001 және 12345 кодтарының ішіндегі ең жақынына дейінгі ең үлкен мүмкін арақашықтық 17-ге тең, оған 270 түрлі код жетеді, мысалы 55570 және 55580. Біріншісі 12345 кодынан 17 қашықтықта, ал екіншісі 00000 кодынан 17 қашықтықта орналасқан.