Edward är grundare och chef för företaget Enigma, tillverkaren av de säkraste kassaskåpen på marknaden. Enigmas kassaskåp skyddas av ett kombinationslås med en 5-siffrig kod. Låset består av fem hjul och en "öppna"-knapp. Varje hjul innehåller alla siffror från 0 till 9 (i denna ordning); efter siffran 9 dyker siffran 0 upp igen.

En operation definieras som att vrida valfritt hjul ett steg i endera riktningen, till exempel att ändra siffran 9 till 8 eller 0. Avståndet mellan två koder är det minsta möjliga antalet operationer som krävs för att ändra en inmatad kod till den andra. Till exempel är avståndet mellan 38911 och 68000 lika med $3 + 0 + 1 + 1 + 1 = 6$.

Kassaskåpstillverkare för statistik över de vanligaste koderna — du får $n$ sådana koder i ordning från mest till minst populär. Enigma är stolta över sin flexibilitet — varje kund kan välja hur många av de $n$ mest populära koderna de vill undvika. Edward väljer sedan en kod som maximerar det minsta avståndet till koderna i det valda prefixet av följden av de mest populära koderna.

För varje $k$ från 1 till $n$ är din uppgift att hitta det största möjliga avståndet från någon kod till den närmaste bland de $k$ mest populära koderna, och räkna hur många koder som uppnår ett sådant avstånd.

Indata

Den första raden innehåller ett heltal $n$ ($1 \le n \le 99\,999$), som anger antalet populära koder.

Var och en av de följande $n$ raderna innehåller en sträng bestående av 5 siffror 0–9, eventuellt med inledande nollor. Detta är de populära koderna i ordning från mest till minst populär. Alla koder är parvis olika.

Utdata

Skriv ut $n$ rader; den $k$-te raden ska innehålla två heltal separerade med mellanslag — det största möjliga avståndet till den närmaste koden bland de $k$ mest populära, samt antalet koder med det avståndet.

Exempel

Indata 1

3
00000
00001
12345

Utdata 1

25 1
24 2
17 270

Indata 2

3
12345
23456
67890

Utdata 2

25 1
22 20
12 15270

Anmärkning

För $k = 1$ är det största möjliga avståndet från koden 00000 lika med 25, vilket endast uppnås av koden 55555.

För $k = 2$ är det största möjliga avståndet till den närmare av koderna 00000 och 00001 lika med 24, vilket uppnås av två koder: 55555 och 55556. Den första ligger på avståndet 24 från 00001, och den andra ligger på avståndet 24 från 00000.

För $k = 3$ är det största möjliga avståndet till den närmaste bland koderna 00000, 00001 och 12345 lika med 17, vilket uppnås av 270 olika koder, till exempel 55570 och 55580. Den första ligger på avståndet 17 från 12345, och den andra ligger på avståndet 17 från 00000.