Edward ist der Gründer und Leiter des Unternehmens Enigma, des Herstellers der sichersten Tresore auf dem Markt. Enigma-Tresore sind durch ein Zahlenschloss mit einem 5-stelligen Code geschützt. Das Schloss besteht aus fünf Rädern und einem „Öffnen“-Knopf. Jedes Rad enthält alle Ziffern von 0 bis 9 (in dieser Reihenfolge); nach der Ziffer 9 erscheint wieder die Ziffer 0.

Eine Operation ist definiert als das Drehen eines beliebigen Rades um eine Position in eine der beiden Richtungen, zum Beispiel das Ändern der Ziffer 9 auf 8 oder 0. Der Abstand zwischen zwei Codes ist die kleinstmögliche Anzahl von Operationen, die erforderlich sind, um einen eingegebenen Code in den anderen umzuwandeln. Beispielsweise beträgt der Abstand zwischen 38911 und 68000 genau $3 + 0 + 1 + 1 + 1 = 6$.

Tresorhersteller führen Statistiken über die am häufigsten verwendeten Codes — Ihnen werden $n$ solche Codes in der Reihenfolge vom beliebtesten zum unbeliebtesten gegeben. Enigma ist stolz auf seine Flexibilität — jeder Kunde kann wählen, wie viele der $n$ beliebtesten Codes er vermeiden möchte. Edward wählt dann einen Code, der den kleinsten Abstand zu den Codes aus dem gewählten Präfix der Folge der beliebtesten Codes maximiert.

Für jedes $k$ von 1 bis $n$ besteht Ihre Aufgabe darin, den größtmöglichen Abstand eines Codes zum nächstgelegenen unter den $k$ beliebtesten Codes zu finden und zu zählen, wie viele Codes einen solchen Abstand erreichen.

Eingabe

Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 99\,999$), die die Anzahl der beliebten Codes angibt.

Jede der folgenden $n$ Zeilen enthält eine Zeichenkette aus 5 Ziffern 0–9, möglicherweise mit führenden Nullen. Dies sind die beliebten Codes in der Reihenfolge vom beliebtesten zum unbeliebtesten. Alle Codes sind paarweise verschieden.

Ausgabe

Geben Sie $n$ Zeilen aus; die $k$-te Zeile sollte zwei durch ein Leerzeichen getrennte ganze Zahlen enthalten — den größtmöglichen Abstand zum nächstgelegenen Code unter den $k$ beliebtesten sowie die Anzahl der Codes mit diesem Abstand.

Beispiele

Eingabe 1

3
00000
00001
12345

Ausgabe 1

25 1
24 2
17 270

Eingabe 2

3
12345
23456
67890

Ausgabe 2

25 1
22 20
12 15270

Hinweis

Für $k = 1$ beträgt der größtmögliche Abstand vom Code 00000 genau 25, was nur vom Code 55555 erreicht wird.

Für $k = 2$ beträgt der größtmögliche Abstand zum näheren der beiden Codes 00000 und 00001 genau 24, was von zwei Codes erreicht wird: 55555 und 55556. Der erste ist 24 von 00001 entfernt, und der zweite ist 24 von 00000 entfernt.

Für $k = 3$ beträgt der größtmögliche Abstand zum nächstgelegenen unter den Codes 00000, 00001 und 12345 genau 17, was von 270 verschiedenen Codes erreicht wird, zum Beispiel 55570 und 55580. Der erste ist 17 von 12345 entfernt, und der zweite ist 17 von 00000 entfernt.