Edward on markkinoiden turvallisimpia kassakaappeja valmistavan Enigma-yhtiön perustaja ja johtaja. Enigman kassakaapit on suojattu yhdistelmälukolla, jossa on 5-numeroinen koodi. Lukko koostuu viidestä kiekosta ja ”avaa”-painikkeesta. Jokaisessa kiekossa on kaikki numerot 0–9 (tässä järjestyksessä); numeron 9 jälkeen tulee jälleen numero 0.

Operaatio määritellään minkä tahansa kiekon pyörittämiseksi yhden pykälän verran kumpaan tahansa suuntaan, esimerkiksi numeron 9 muuttamiseksi numeroksi 8 tai 0. Kahden koodin välinen etäisyys on pienin mahdollinen määrä operaatioita, jotka tarvitaan toisen syötetyn koodin muuttamiseksi toiseksi. Esimerkiksi koodien 38911 ja 68000 välinen etäisyys on $3 + 0 + 1 + 1 + 1 = 6$.

Kassakaappien valmistajat pitävät tilastoa yleisimmin käytetyistä koodeista — saat $n$ tällaista koodia järjestyksessä suosituimmasta vähiten suosittuun. Enigma on ylpeä joustavuudestaan — jokainen asiakas voi valita, kuinka monta $n$:stä suosituimmasta koodista hän haluaa välttää. Tämän jälkeen Edward valitsee koodin, joka maksimoi pienimmän etäisyyden suosituimpien koodien jonon valitun alkuosan koodeihin.

Tehtäväsi on jokaiselle $k$ väliltä 1 – $n$ etsiä suurin mahdollinen etäisyys jostakin koodista lähimpään $k$:n suosituimman koodin joukossa sekä laskea, kuinka moni koodi saavuttaa tällaisen etäisyyden.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 99\,999$), joka ilmaisee suosittujen koodien määrän.

Jokainen seuraavista $n$ rivistä sisältää merkkijonon, joka koostuu viidestä numerosta 0–9, mahdollisesti etunollilla. Nämä ovat suositut koodit järjestyksessä suosituimmasta vähiten suosittuun. Kaikki koodit ovat pareittain erisuuria.

Tuloste

Tulosta $n$ riviä; $k$:nnen rivin tulee sisältää kaksi välilyönnillä erotettua kokonaislukua — suurin mahdollinen etäisyys lähimpään koodiin $k$:n suosituimman joukossa sekä tällaisten koodien lukumäärä.

Esimerkit

Syöte 1

3
00000
00001
12345

Tuloste 1

25 1
24 2
17 270

Syöte 2

3
12345
23456
67890

Tuloste 2

25 1
22 20
12 15270

Huomautus

Kun $k = 1$, suurin mahdollinen etäisyys koodista 00000 on 25, jonka saavuttaa vain koodi 55555.

Kun $k = 2$, suurin mahdollinen etäisyys lähempään koodeista 00000 ja 00001 on 24, jonka saavuttaa kaksi koodia: 55555 ja 55556. Ensimmäinen on etäisyydellä 24 koodista 00001 ja toinen etäisyydellä 24 koodista 00000.

Kun $k = 3$, suurin mahdollinen etäisyys lähimpään koodeista 00000, 00001 ja 12345 on 17, jonka saavuttaa 270 eri koodia, esimerkiksi 55570 ja 55580. Ensimmäinen on etäisyydellä 17 koodista 12345 ja toinen etäisyydellä 17 koodista 00000.