あなたの住む小さな都市は、新しい社会保障番号（SSN）システムを導入する予定である。各市民は5桁の SSN で識別される。最初の4桁は基本 ID 番号（0000–9999）を示し、最後の1桁は誤りを検出するための検査数字である。
検査数字の計算に、都市は演算表を使うことにした。演算表は対角成分がすべて $0$ である、十進数字の $10\times10$ の表である。以下に2つの演算表の例を示す。
演算表1
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | |
|---|---|---|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $3$ | $1$ | $7$ | $5$ | $9$ | $8$ | $6$ | $4$ | $2$ |
| $1$ | $7$ | $0$ | $9$ | $2$ | $1$ | $5$ | $4$ | $8$ | $6$ | $3$ |
| $2$ | $4$ | $2$ | $0$ | $6$ | $8$ | $7$ | $1$ | $3$ | $5$ | $9$ |
| $3$ | $1$ | $7$ | $5$ | $0$ | $9$ | $8$ | $3$ | $4$ | $2$ | $6$ |
| $4$ | $6$ | $1$ | $2$ | $3$ | $0$ | $4$ | $5$ | $9$ | $7$ | $8$ |
| $5$ | $3$ | $6$ | $7$ | $4$ | $2$ | $0$ | $9$ | $5$ | $8$ | $1$ |
| $6$ | $5$ | $8$ | $6$ | $9$ | $7$ | $2$ | $0$ | $1$ | $3$ | $4$ |
| $7$ | $8$ | $9$ | $4$ | $5$ | $3$ | $6$ | $2$ | $0$ | $1$ | $7$ |
| $8$ | $9$ | $4$ | $3$ | $8$ | $6$ | $1$ | $7$ | $2$ | $0$ | $5$ |
| $9$ | $2$ | $5$ | $8$ | $1$ | $4$ | $3$ | $6$ | $7$ | $9$ | $0$ |
演算表2
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | |
|---|---|---|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ |
| $1$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ |
| $2$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
| $3$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| $4$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ |
| $5$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ |
| $6$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ |
| $7$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ |
| $8$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ |
| $9$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ |
演算表を使うと、4桁の基本 ID 番号 $abcd$ の検査数字 $e$ は次の式で計算される。ここで $i\otimes j$ は表の第 $i$ 行、第 $j$ 列の成分を表す。
$$e=(((0\otimes a)\otimes b)\otimes c)\otimes d$$
例えば演算表1を用いると、基本 ID 番号 $abcd=2016$ の検査数字 $e$ は次のように計算される。
$$\begin{aligned}e&=(((0\otimes2)\otimes0)\otimes1)\otimes6\\&=((1\otimes0)\otimes1)\otimes6\\&=(7\otimes1)\otimes6\\&=9\otimes6\\&=6\end{aligned}$$
したがって SSN は20166となる。
検査数字は使用する演算表によって変わることに注意せよ。演算表2では、同じ基本 ID 番号2016に対して $e=3$ となり、SSN 全体は20163となる。
図 B.1。よくある人為的誤りの2種類
検査数字を追加する目的は、SSN を書いたり入力したりするときの人為的誤りを検出することである。次の検査関数は一部の人為的誤りを検出できる。5桁の番号 $abcde$ に対し、検査関数を次のように定義する。
$$\operatorname{check}(abcde)=((((0\otimes a)\otimes b)\otimes c)\otimes d)\otimes e$$
正しい SSN に対し、この関数は $0$ を返す。演算表のすべての対角成分が $0$ であり、正しい SSN では $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.$$
一方、$\operatorname{check}$ が $0$ 以外の値を返した場合、与えられた番号は正しい SSN ではあり得ない。使用する演算表によっては、誤った SSN に対しても検査関数が $0$ を返すことに注意せよ。検出される誤りの種類は使用する演算表に依存し、表が誤り検出の品質を決める。
市当局は図 B.1 に示すように、数字列におけるよくある人為的誤りの2種類、すなわち1つの数字を変更することと隣接する2つの数字を入れ替えることを検出したい。
4桁の基本 ID 番号0000–9999から作られるすべての SSN において、この2種類のよくある誤りをすべて検出できる演算表を良いとする。基本 ID の4桁だけでなく、検査数字における誤りも検出する必要がある。例えば演算表1は良い。演算表2は良くない。正しい SSN 20163の3桁目と4桁目を入れ替えて得られる20613に対して $\operatorname{check}(20613)=0$ となるからである。実際、10000個の基本 ID 番号のうち、演算表2は3439個もの番号について、少なくとも1つのよくある誤りを検出できない。
演算表が与えられる。この表が少なくとも1つのよくある誤りを検出できない基本 ID 番号の個数を数えることで、表の良さを判定せよ。
入力
入力は次の形式の1つのテストケースからなる。
$$\begin{array}{cccc}x_{00}&x_{01}&\cdots&x_{09}\\\vdots\\x_{90}&x_{91}&\cdots&x_{99}\end{array}$$
入力は演算表を表し、$x_{ij}$ は第 $i$ 行、第 $j$ 列の十進数字である。各行は表の1行に対応し、成分は1個の空白で区切られる。対角成分 $x_{ii}$（$i=0,\ldots,9$）は常に $0$ である。
出力
与えられた表が少なくとも1つのよくある人為的誤りを検出できない基本 ID 番号の個数を出力せよ。
入出力例
入力 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
出力 1
0
入力 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
出力 2
3439
入力 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
出力 3
9995
入力 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
出力 4
10000