Edward è il fondatore e direttore dell'azienda Enigma, il produttore delle casseforti più sicure sul mercato. Le casseforti Enigma sono protette da una serratura a combinazione con un codice a 5 cifre. La serratura è composta da cinque rotelle e da un pulsante "apri". Ogni rotella contiene tutte le cifre da 0 a 9 (in quest'ordine); dopo la cifra 9 compare nuovamente la cifra 0.

Un'operazione è definita come la rotazione di una qualsiasi rotella di una posizione in una delle due direzioni, ad esempio cambiando la cifra 9 in 8 oppure in 0. La distanza tra due codici è il minimo numero possibile di operazioni necessarie per trasformare un codice inserito nell'altro. Ad esempio, la distanza tra 38911 e 68000 è $3 + 0 + 1 + 1 + 1 = 6$.

I produttori di casseforti tengono statistiche sui codici più comunemente usati — ti vengono dati $n$ di questi codici in ordine dal più popolare al meno popolare. Enigma è orgogliosa della propria flessibilità — ogni cliente può scegliere quanti tra gli $n$ codici più popolari desidera evitare. Edward sceglie quindi un codice che massimizza la distanza minima dai codici appartenenti al prefisso selezionato della sequenza dei codici più popolari.

Per ogni $k$ da 1 a $n$, il tuo compito è trovare la massima distanza possibile di un qualche codice dal più vicino tra i $k$ codici più popolari, e contare quanti codici raggiungono tale distanza.

Input

La prima riga contiene un intero $n$ ($1 \le n \le 99\,999$), che indica il numero di codici popolari.

Ciascuna delle seguenti $n$ righe contiene una stringa composta da 5 cifre 0–9, eventualmente con zeri iniziali. Questi sono i codici popolari in ordine dal più popolare al meno popolare. Tutti i codici sono distinti a due a due.

Output

Stampa $n$ righe; la $k$-esima riga deve contenere due interi separati da uno spazio — la massima distanza possibile dal codice più vicino tra i $k$ più popolari, e il numero di codici con tale distanza.

Esempi

Input 1

3
00000
00001
12345

Output 1

25 1
24 2
17 270

Input 2

3
12345
23456
67890

Output 2

25 1
22 20
12 15270

Note

Per $k = 1$, la massima distanza possibile dal codice 00000 è 25, raggiunta solo dal codice 55555.

Per $k = 2$, la massima distanza possibile dal più vicino tra i codici 00000 e 00001 è 24, raggiunta da due codici: 55555 e 55556. Il primo dista 24 da 00001, e il secondo dista 24 da 00000.

Per $k = 3$, la massima distanza possibile dal più vicino tra i codici 00000, 00001 e 12345 è 17, raggiunta da 270 codici diversi, ad esempio 55570 e 55580. Il primo dista 17 da 12345, e il secondo dista 17 da 00000.