La petite ville où vous habitez prévoit d'introduire un nouveau système de numéros de sécurité sociale (SSN). Chaque citoyen sera identifié par un SSN à cinq chiffres. Ses quatre premiers chiffres indiquent le numéro d'identification de base (0000–9999) et le dernier chiffre est un chiffre de contrôle permettant de détecter les erreurs.

Pour calculer les chiffres de contrôle, la ville a décidé d'utiliser une table d'opération. Une table d'opération est un tableau $10 \times 10$ de chiffres décimaux dont tous les éléments diagonaux valent $0$. Voici ci-dessous deux exemples de tables d'opération.

Table d'opération 1

Table d'opération 2

À l'aide d'une table d'opération, le chiffre de contrôle $e$ pour un numéro d'identification de base à quatre chiffres $abcd$ est calculé par la formule suivante. Ici, $i \otimes j$ désigne l'élément de la table situé à la ligne $i$ et à la colonne $j$.

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

Par exemple, en utilisant la Table d'opération 1, le chiffre de contrôle $e$ pour le numéro d'identification de base $abcd = 2016$ se calcule de la manière suivante.

$$\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}$$

Ainsi, le SSN est $20166$.

Notez que le chiffre de contrôle dépend de la table d'opération utilisée. Avec la Table d'opération 2, on obtient $e = 3$ pour le même numéro d'identification de base $2016$, et le SSN complet sera $20163$.

$$\begin{array}{c} \begin{aligned} 2016 & \\ \Downarrow & \; \text{+chiffre de contrôle avec la Table d'opération 2} \\ 20163 & \\ \Downarrow & \; \text{erreurs humaines} \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{Modification d'un seul chiffre}} \\[10pt] \overbrace{\mathbf{02}163 \quad 2\mathbf{10}63 \quad 20\mathbf{61}3 \quad 201\mathbf{36}}^{\text{Transposition de deux chiffres adjacents}} \end{array}} \end{array}$$

Le but de l'ajout du chiffre de contrôle est de détecter les erreurs humaines lors de l'écriture ou de la saisie des SSN. La fonction check suivante permet de détecter certaines erreurs humaines. Pour un nombre à cinq chiffres $abcde$, la fonction check est définie comme suit.

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

Cette fonction renvoie $0$ pour un SSN correct. En effet, chaque élément diagonal d'une table d'opération vaut $0$ et, pour un SSN correct, on a $e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$ :

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

En revanche, une valeur non nulle renvoyée par check indique que le nombre donné ne peut pas être un SSN correct. Notez que, selon la table d'opération utilisée, la fonction check peut renvoyer $0$ pour un SSN incorrect. Les types d'erreurs détectées dépendent de la table d'opération utilisée ; c'est la table qui détermine la qualité de la détection d'erreurs.

Les autorités municipales souhaitent détecter deux types d'erreurs humaines courantes sur les suites de chiffres : la modification d'un seul chiffre et la transposition de deux chiffres adjacents, comme illustré à la Figure B.1.

Une table d'opération est dite bonne si elle permet de détecter toutes les erreurs courantes de ces deux types sur tous les SSN formés à partir des numéros d'identification de base à quatre chiffres 0000–9999. Notez que les erreurs portant sur le chiffre de contrôle, tout comme celles portant sur les quatre chiffres de l'identifiant de base, doivent être détectées. Par exemple, la Table d'opération 1 est bonne. La Table d'opération 2 n'est pas bonne car, pour $20613$, qui est un nombre obtenu en transposant les 3e et 4e chiffres d'un SSN correct $20163$, $\operatorname{check}(20613)$ vaut $0$. En réalité, parmi les $10000$ numéros d'identification de base, la Table d'opération 2 ne parvient pas à détecter une ou plusieurs erreurs courantes pour pas moins de $3439$ numéros d'identification de base.

Étant donné une table d'opération, déterminez sa qualité en comptant le nombre de numéros d'identification de base pour lesquels la table donnée ne parvient pas à détecter une ou plusieurs erreurs courantes.

Entrée

L'entrée est constituée d'un unique cas de test au format suivant.

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

L'entrée décrit une table d'opération où $x_{ij}$ est le chiffre décimal situé à la ligne $i$ et à la colonne $j$. Chaque ligne de l'entrée correspond à une ligne de la table, dans laquelle les éléments sont séparés par une seule espace. Les éléments diagonaux $x_{ii}$ ($i = 0, \ldots, 9$) valent toujours $0$.

Sortie

Affichez le nombre de numéros d'identification de base pour lesquels la table donnée ne parvient pas à détecter une ou plusieurs erreurs humaines courantes.

Exemples

Entrée 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

Sortie 1

0

Entrée 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

Sortie 2

3439

Entrée 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

Sortie 3

9995

Entrée 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

Sortie 4

10000