Edward er stofnandi og forstjóri fyrirtækisins Enigma, framleiðanda öruggustu peningaskápa á markaðnum. Enigma-peningaskápar eru varðir með talnalás með 5 stafa kóða. Lásinn samanstendur af fimm hjólum og „opna“-hnappi. Hvert hjól inniheldur alla tölustafi frá 0 til 9 (í þessari röð); á eftir tölustafnum 9 kemur tölustafurinn 0 aftur.

Ein aðgerð er skilgreind sem svo að einu hjóli sé snúið um eina stöðu í hvora áttina sem er, til dæmis að breyta tölustafnum 9 í 8 eða 0. Fjarlægðin milli tveggja kóða er lágmarksfjöldi aðgerða sem þarf til að breyta öðrum innslegnum kóða í hinn. Til dæmis er fjarlægðin milli 38911 og 68000 jöfn $3 + 0 + 1 + 1 + 1 = 6$.

Framleiðendur peningaskápa halda tölfræði yfir algengustu kóðana — þér eru gefnir $n$ slíkir kóðar í röð frá þeim vinsælasta til þess síðst vinsæla. Enigma leggur metnað sinn í sveigjanleika — hver viðskiptavinur getur valið hversu marga af $n$ vinsælustu kóðunum hann vill forðast. Edward velur þá kóða sem hámarkar minnstu fjarlægðina í kóðana úr völdu forskeyti rununnar af vinsælustu kóðunum.

Fyrir hvert $k$ frá 1 til $n$ er verkefni þitt að finna mestu mögulegu fjarlægð einhvers kóða frá þeim næsta meðal $k$ vinsælustu kóðanna, og telja hversu margir kóðar ná slíkri fjarlægð.

Inntak

Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 99\,999$), sem táknar fjölda vinsælla kóða.

Hver af næstu $n$ línum inniheldur streng sem samanstendur af 5 tölustöfum 0–9, hugsanlega með fremri núllum. Þetta eru vinsælu kóðarnir í röð frá þeim vinsælasta til þess síðst vinsæla. Allir kóðar eru innbyrðis ólíkir.

Úttak

Skrifið út $n$ línur; $k$-ta línan á að innihalda tvær heiltölur aðskildar með bili — mestu mögulegu fjarlægðina í næsta kóða meðal $k$ vinsælustu kóðanna, og fjölda kóða með þá fjarlægð.

Dæmi

Inntak 1

3
00000
00001
12345

Úttak 1

25 1
24 2
17 270

Inntak 2

3
12345
23456
67890

Úttak 2

25 1
22 20
12 15270

Athugasemd

Fyrir $k = 1$ er mesta mögulega fjarlægðin frá kóðanum 00000 jöfn 25, sem næst aðeins með kóðanum 55555.

Fyrir $k = 2$ er mesta mögulega fjarlægðin í þann kóða sem nær er af 00000 og 00001 jöfn 24, sem næst með tveimur kóðum: 55555 og 55556. Sá fyrri er í fjarlægðinni 24 frá 00001, og sá síðari er í fjarlægðinni 24 frá 00000.

Fyrir $k = 3$ er mesta mögulega fjarlægðin í þann næsta meðal kóðanna 00000, 00001 og 12345 jöfn 17, sem næst með 270 ólíkum kóðum, til dæmis 55570 og 55580. Sá fyrri er í fjarlægðinni 17 frá 12345, og sá síðari er í fjarlægðinni 17 frá 00000.