Quality of Check Digits

Time Limit : 1 sec, Memory Limit : 262144 KB

Problem B Quality of Check Digits

The small city where you live plans to introduce a new social security number (SSN) system. Each citizen will be identified by a five-digit SSN. Its first four digits indicate the basic ID number (0000 - 9999) and the last one digit is a check digit for detecting errors.

For computing check digits, the city has decided to use an operation table. An operation table is a 10 $\times$ 10 table of decimal digits whose diagonal elements are all 0. Below are two example operation tables.

Operation Table 1      Operation Table 2
    

Using an operation table, the check digit $e$ for a four-digit basic ID number $abcd$ is computed by using the following formula. Here, $i \otimes j$ denotes the table element at row $i$ and column $j$.

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

For example, by using Operation Table 1 the check digit $e$ for a basic ID number $abcd = $ 2016 is computed in the following way.

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

Thus, the SSN is 20166.

Note that the check digit depends on the operation table used. With Operation Table 2, we have $e = $ 3 for the same basic ID number 2016, and the whole SSN will be 20163.


Figure B.1. Two kinds of common human errors

The purpose of adding the check digit is to detect human errors in writing/typing SSNs. The following check function can detect certain human errors. For a five-digit number $abcde$, the check function is defined as follows.

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

This function returns 0 for a correct SSN. This is because every diagonal element in an operation table is 0 and for a correct SSN we have $e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$:

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

On the other hand, a non-zero value returned by check indicates that the given number cannot be a correct SSN. Note that, depending on the operation table used, check function may return 0 for an incorrect SSN. Kinds of errors detected depends on the operation table used; the table decides the quality of error detection.

The city authority wants to detect two kinds of common human errors on digit sequences: altering one single digit and transposing two adjacent digits, as shown in Figure B.1.

An operation table is good if it can detect all the common errors of the two kinds on all SSNs made from four-digit basic ID numbers 0000{9999. Note that errors with the check digit, as well as with four basic ID digits, should be detected. For example, Operation Table 1 is good. Operation Table 2 is not good because, for 20613, which is a number obtained by transposing the 3rd and the 4th digits of a correct SSN 20163, check(20613) is 0. Actually, among 10000 basic ID numbers, Operation Table 2 cannot detect one or more common errors for as many as 3439 basic ID numbers.

Given an operation table, decide how good it is by counting the number of basic ID numbers for which the given table cannot detect one or more common errors.

Input

The input consists of a single test case of the following format.

$x_{00}$ $x_{01}$ ... $x_{09}$
...
$x_{90}$ $x_{91}$ ... $x_{99}$

The input describes an operation table with $x_{ij}$ being the decimal digit at row $i$ and column $j$. Each line corresponds to a row of the table, in which elements are separated by a single space. The diagonal elements $x_{ii}$ ($i = 0, ... , 9$) are always 0.

Output

Output the number of basic ID numbers for which the given table cannot detect one or more common human errors.

Sample Input 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

Sample Output 1

0

Sample Input 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

Sample Output 2

3439

Sample Input 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

Sample Output 3

9995

Sample Input 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

Sample Output 4

10000

Source: ACM International Collegiate Programming Contest , Asia Regional Tsukuba, Tsukuba, Japan, 2016-10-16
http://icpc.iisf.or.jp/2016-tsukuba/