Die Kleinstadt, in der du lebst, plant die Einführung eines neuen Sozialversicherungsnummern-Systems (SSN). Jeder Bürger wird durch eine fünfstellige SSN identifiziert. Die ersten vier Ziffern geben die Basis-ID-Nummer (0000–9999) an, und die letzte Ziffer ist eine Prüfziffer zur Fehlererkennung.

Zur Berechnung der Prüfziffern hat die Stadt beschlossen, eine Verknüpfungstafel zu verwenden. Eine Verknüpfungstafel ist eine $10 \times 10$-Tabelle aus Dezimalziffern, deren Diagonalelemente alle $0$ sind. Unten sind zwei Beispiele für Verknüpfungstafeln angegeben.

Verknüpfungstafel 1

Verknüpfungstafel 2

Mithilfe einer Verknüpfungstafel wird die Prüfziffer $e$ für eine vierstellige Basis-ID-Nummer $abcd$ nach der folgenden Formel berechnet. Hierbei bezeichnet $i \otimes j$ den Tabelleneintrag in Zeile $i$ und Spalte $j$.

$$e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$$

Beispielsweise wird unter Verwendung von Verknüpfungstafel 1 die Prüfziffer $e$ für die Basis-ID-Nummer $abcd = 2016$ wie folgt berechnet.

$$\begin{aligned} e &= (((0 \otimes 2) \otimes 0) \otimes 1) \otimes 6 \\ &= ((1 \otimes 0) \otimes 1) \otimes 6 \\ &= (7 \otimes 1) \otimes 6 \\ &= 9 \otimes 6 \\ &= 6 \end{aligned}$$

Somit lautet die SSN $20166$.

Beachte, dass die Prüfziffer von der verwendeten Verknüpfungstafel abhängt. Mit Verknüpfungstafel 2 erhalten wir für dieselbe Basis-ID-Nummer $2016$ den Wert $e = 3$, und die gesamte SSN lautet $20163$.

$$\begin{array}{c} \begin{aligned} 2016 & \\ \Downarrow & \; \text{+Prüfziffer gemäß Verknüpfungstafel 2} \\ 20163 & \\ \Downarrow & \; \text{menschliche Fehler} \end{aligned} \\[6pt] \boxed{\begin{array}{c} \overbrace{\mathbf{0}0163 \quad \mathbf{1}0163 \quad \dots \quad \mathbf{9}0163 \quad 2\mathbf{1}163 \quad 2\mathbf{2}163 \quad \dots \quad 2016\mathbf{8} \quad 2016\mathbf{9}}^{\text{Abändern einer einzelnen Ziffer}} \\[10pt] \overbrace{\mathbf{02}163 \quad 2\mathbf{10}63 \quad 20\mathbf{61}3 \quad 201\mathbf{36}}^{\text{Vertauschen zweier benachbarter Ziffern}} \end{array}} \end{array}$$

Der Zweck des Hinzufügens der Prüfziffer besteht darin, menschliche Fehler beim Aufschreiben oder Eintippen von SSNs zu erkennen. Die folgende Funktion check kann bestimmte menschliche Fehler erkennen. Für eine fünfstellige Zahl $abcde$ ist die Funktion check wie folgt definiert.

$$\operatorname{check}(abcde) = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e$$

Diese Funktion liefert für eine korrekte SSN den Wert $0$. Das liegt daran, dass jedes Diagonalelement einer Verknüpfungstafel $0$ ist und für eine korrekte SSN $e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$ gilt:

$$\operatorname{check}(abcde) = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e = e \otimes e = 0.$$

Andererseits zeigt ein von check zurückgegebener Wert ungleich null an, dass die gegebene Zahl keine korrekte SSN sein kann. Beachte, dass die Funktion check je nach verwendeter Verknüpfungstafel auch für eine fehlerhafte SSN den Wert $0$ liefern kann. Welche Arten von Fehlern erkannt werden, hängt von der verwendeten Verknüpfungstafel ab; die Tafel bestimmt die Qualität der Fehlererkennung.

Die Stadtverwaltung möchte zwei Arten häufiger menschlicher Fehler in Ziffernfolgen erkennen: das Abändern einer einzelnen Ziffer und das Vertauschen zweier benachbarter Ziffern, wie in Abbildung B.1 dargestellt.

Eine Verknüpfungstafel heißt gut, wenn sie alle häufigen Fehler dieser beiden Arten bei allen SSNs erkennen kann, die aus den vierstelligen Basis-ID-Nummern 0000–9999 gebildet werden. Beachte, dass Fehler in der Prüfziffer ebenso erkannt werden müssen wie Fehler in den vier Ziffern der Basis-ID. Beispielsweise ist Verknüpfungstafel 1 gut. Verknüpfungstafel 2 ist nicht gut, da für $20613$ – eine Zahl, die durch Vertauschen der 3. und 4. Ziffer der korrekten SSN $20163$ entsteht – $\operatorname{check}(20613)$ gleich $0$ ist. Tatsächlich kann Verknüpfungstafel 2 unter den $10000$ Basis-ID-Nummern bei nicht weniger als $3439$ Basis-ID-Nummern einen oder mehrere häufige Fehler nicht erkennen.

Bestimme für eine gegebene Verknüpfungstafel, wie gut sie ist, indem du die Anzahl der Basis-ID-Nummern zählst, bei denen die gegebene Tafel einen oder mehrere häufige Fehler nicht erkennen kann.

Eingabe

Die Eingabe besteht aus einem einzigen Testfall im folgenden Format.

$$\begin{array}{cccc} x_{00} & x_{01} & \cdots & x_{09} \\ \vdots & & & \\ x_{90} & x_{91} & \cdots & x_{99} \end{array}$$

Die Eingabe beschreibt eine Verknüpfungstafel, wobei $x_{ij}$ die Dezimalziffer in Zeile $i$ und Spalte $j$ ist. Jede Zeile entspricht einer Zeile der Tafel, in der die Elemente durch jeweils ein einzelnes Leerzeichen getrennt sind. Die Diagonalelemente $x_{ii}$ ($i = 0, \ldots, 9$) sind stets $0$.

Ausgabe

Gib die Anzahl der Basis-ID-Nummern aus, für die die gegebene Tafel einen oder mehrere häufige menschliche Fehler nicht erkennen kann.

Beispiele

Eingabe 1

0 3 1 7 5 9 8 6 4 2
7 0 9 2 1 5 4 8 6 3
4 2 0 6 8 7 1 3 5 9
1 7 5 0 9 8 3 4 2 6
6 1 2 3 0 4 5 9 7 8
3 6 7 4 2 0 9 5 8 1
5 8 6 9 7 2 0 1 3 4
8 9 4 5 3 6 2 0 1 7
9 4 3 8 6 1 7 2 0 5
2 5 8 1 4 3 6 7 9 0

Ausgabe 1

0

Eingabe 2

0 1 2 3 4 5 6 7 8 9
9 0 1 2 3 4 5 6 7 8
8 9 0 1 2 3 4 5 6 7
7 8 9 0 1 2 3 4 5 6
6 7 8 9 0 1 2 3 4 5
5 6 7 8 9 0 1 2 3 4
4 5 6 7 8 9 0 1 2 3
3 4 5 6 7 8 9 0 1 2
2 3 4 5 6 7 8 9 0 1
1 2 3 4 5 6 7 8 9 0

Ausgabe 2

3439

Eingabe 3

0 9 8 7 6 5 4 3 2 1
1 0 9 8 7 6 5 4 3 2
2 1 0 9 8 7 6 5 4 3
3 2 1 0 9 8 7 6 5 4
4 3 2 1 0 9 8 7 6 5
5 4 3 2 1 0 9 8 7 6
6 5 4 3 2 1 0 9 8 7
7 6 5 4 3 2 1 0 9 8
8 7 6 5 4 3 2 1 0 9
9 8 7 6 5 4 3 2 1 0

Ausgabe 3

9995

Eingabe 4

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Ausgabe 4

10000