Edward er grunnlegger og leder av selskapet Enigma, produsenten av de sikreste safene på markedet. Enigma-safer er beskyttet av en kombinasjonslås med en 5-sifret kode. Låsen består av fem hjul og en «åpne»-knapp. Hvert hjul inneholder alle sifrene fra 0 til 9 (i denne rekkefølgen); etter sifferet 9 dukker sifferet 0 opp igjen.

En operasjon er definert som å dreie et hvilket som helst hjul én posisjon i en av retningene, for eksempel å endre sifferet 9 til 8 eller 0. Avstanden mellom to koder er det minste mulige antallet operasjoner som kreves for å endre én inntastet kode til den andre. For eksempel er avstanden mellom 38911 og 68000 lik $3 + 0 + 1 + 1 + 1 = 6$.

Safeprodusenter fører statistikk over de mest brukte kodene — du får oppgitt $n$ slike koder i rekkefølge fra mest til minst populær. Enigma er stolte av sin fleksibilitet — hver kunde kan velge hvor mange av de $n$ mest populære kodene de ønsker å unngå. Edward velger deretter en kode som maksimerer den minste avstanden til kodene fra det valgte prefikset i følgen av de mest populære kodene.

For hver $k$ fra 1 til $n$ er oppgaven din å finne den største mulige avstanden fra en kode til den nærmeste blant de $k$ mest populære kodene, og telle hvor mange koder som oppnår en slik avstand.

Inndata

Den første linjen inneholder et heltall $n$ ($1 \le n \le 99\,999$), som angir antallet populære koder.

Hver av de påfølgende $n$ linjene inneholder en streng bestående av 5 sifre 0–9, muligens med ledende nuller. Dette er de populære kodene i rekkefølge fra mest til minst populær. Alle koder er parvis forskjellige.

Utdata

Skriv ut $n$ linjer; den $k$-te linjen skal inneholde to heltallatskilt med mellomrom — den største mulige avstanden til den nærmeste koden blant de $k$ mest populære, og antallet koder med denne avstanden.

Eksempler

Inndata 1

3
00000
00001
12345

Utdata 1

25 1
24 2
17 270

Inndata 2

3
12345
23456
67890

Utdata 2

25 1
22 20
12 15270

Merk

For $k = 1$ er den største mulige avstanden fra koden 00000 lik 25, oppnådd kun av koden 55555.

For $k = 2$ er den største mulige avstanden til den nærmeste av kodene 00000 og 00001 lik 24, oppnådd av to koder: 55555 og 55556. Den første har avstand 24 fra 00001, og den andre har avstand 24 fra 00000.

For $k = 3$ er den største mulige avstanden til den nærmeste blant kodene 00000, 00001 og 12345 lik 17, oppnådd av 270 forskjellige koder, for eksempel 55570 og 55580. Den første har avstand 17 fra 12345, og den andre har avstand 17 fra 00000.