{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2\u003eProblem B\n\n\u003c/h2\u003e\n\n\u003cp\u003e\nThe 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 \u003ci\u003echeck digit\u003c/i\u003e for detecting errors.\n\u003c/p\u003e\n\n\u003cp\u003e\nFor 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.\n\u003c/p\u003e\n\n\u003ccenter\u003e\n\u003ctable\u003e\n\u003ctbody\u003e\u003ctr\u003e\n\u003ctd\u003e\nOperation Table 1\n\u003c/td\u003e\n\u003ctd\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n\u003ctd\u003e\nOperation Table 2\n\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/d27c4a7aac5d3ded94c4e5b2dee2b640?v\u003d1716006978\"\u003e\n\u003c/td\u003e\n\u003ctd\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n\u003ctd\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/58289c1d8bb452078f176ae68920275e?v\u003d1716006978\"\u003e\n\u003c/td\u003e\n\u003c/tr\u003e\n\u003c/tbody\u003e\u003c/table\u003e\n\u003c/center\u003e\n\u003cbr\u003e\n\n\u003cp\u003e\nUsing 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\n j$ denotes the table element at row $i$ and column $j$.\u003cbr\u003e\n\u003cbr\u003e\n\n$e \u003d (((0 \\otimes a) \\otimes b) \\otimes c) \\otimes d$\n\n\u003cbr\u003e\u003cbr\u003e\n\nFor example, by using Operation Table 1 the check digit $e$ for a basic ID number $abcd \u003d $ 2016 is computed in the following way.\u003cbr\u003e\n\u003cbr\u003e\n\n$e \u003d (((0 \\otimes 2) \\otimes 0) \\otimes 1) \\otimes 6$\u003cbr\u003e\n$\\;\\;\\; \u003d (( \\;\\;\\;\\;\\;\\;\\;\\;\\; 1 \\otimes 0) \\otimes 1) \\otimes 6$\u003cbr\u003e\n$\\;\\;\\; \u003d ( \\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\; 7 \\otimes 1) \\otimes 6$\u003cbr\u003e\n$\\;\\;\\; \u003d \\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\; 9 \\otimes 6$\u003cbr\u003e\n$\\;\\;\\; \u003d \\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\; 6$\u003cbr\u003e\n\u003cbr\u003e\n\nThus, the SSN is 20166.\n\u003c/p\u003e\n\n\u003cp\u003e\nNote that the check digit depends on the operation table used. With Operation Table 2, we have $e \u003d $ 3 for the same basic ID number 2016, and the whole SSN will be 20163.\n\u003c/p\u003e\n\n\n\u003ccenter\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/a5989554f31237498abee68d38006629?v\u003d1716006978\"\u003e\u003cbr\u003e\nFigure B.1. Two kinds of common human errors\n\u003c/center\u003e\u003cbr\u003e\n\n\u003cp\u003e\nThe purpose of adding the check digit is to detect human errors in writing/typing SSNs. The following \u003cspan\u003echeck\u003c/span\u003e function can detect certain human errors. For a five-digit number $abcde$, the check function is defined as follows.\n\u003c/p\u003e\n\n\u003ccenter\u003e\n\u003cspan\u003echeck\u003c/span\u003e($abcde$) $ \u003d ((((0 \\otimes a) \\otimes b) \\otimes c) \\otimes d) \\otimes e$\u003cbr\u003e\n\u003c/center\u003e\n\u003cbr\u003e\n\n\u003cp\u003e\nThis 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 \u003d (((0 \\otimes a) \\otimes b) \\otimes c) \\otimes d$:\u003cbr\u003e\n\u003c/p\u003e\n\n\u003ccenter\u003e\n\u003cspan\u003echeck\u003c/span\u003e($abcde$) $ \u003d ((((0 \\otimes a) \\otimes b) \\otimes c) \\otimes d) \\otimes e \u003d e \\otimes e \u003d 0$\u003cbr\u003e\n\u003c/center\u003e\n\u003cbr\u003e\n\n\u003cp\u003e\nOn 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.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe 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. \n\u003c/p\u003e\n\n\u003cp\u003e\nAn 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, \u003cspan\u003echeck\u003c/span\u003e(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.\n\u003c/p\u003e\n\n\u003cp\u003e\nGiven 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.\n\u003c/p\u003e\n\n\n\n\n\n\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cp\u003e\nThe input consists of a single test case of the following format.\u003cbr\u003e\n\u003cbr\u003e\n$x_{00}$ $x_{01}$ ... $x_{09}$\u003cbr\u003e\n...\u003cbr\u003e\n$x_{90}$ $x_{91}$ ... $x_{99}$\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cp\u003e\nThe 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 \u003d 0, ... , 9$) are always 0.\n\u003c/p\u003e\n\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\n\u003cp\u003e\nOutput the number of basic ID numbers for which the given table cannot detect one or more common human errors.\n\u003c/p\u003e\n\n\n\n\u003ch3\u003eSample Input 1\u003c/h3\u003e\n\n\u003cpre\u003e0 3 1 7 5 9 8 6 4 2\n7 0 9 2 1 5 4 8 6 3\n4 2 0 6 8 7 1 3 5 9\n1 7 5 0 9 8 3 4 2 6\n6 1 2 3 0 4 5 9 7 8\n3 6 7 4 2 0 9 5 8 1\n5 8 6 9 7 2 0 1 3 4\n8 9 4 5 3 6 2 0 1 7\n9 4 3 8 6 1 7 2 0 5\n2 5 8 1 4 3 6 7 9 0\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 1\u003c/h3\u003e\n\n\u003cpre\u003e0\u003c/pre\u003e\n\n\u003cbr\u003e\n\n\u003ch3\u003eSample Input 2\u003c/h3\u003e\n\n\u003cpre\u003e0 1 2 3 4 5 6 7 8 9\n9 0 1 2 3 4 5 6 7 8\n8 9 0 1 2 3 4 5 6 7\n7 8 9 0 1 2 3 4 5 6\n6 7 8 9 0 1 2 3 4 5\n5 6 7 8 9 0 1 2 3 4\n4 5 6 7 8 9 0 1 2 3\n3 4 5 6 7 8 9 0 1 2\n2 3 4 5 6 7 8 9 0 1\n1 2 3 4 5 6 7 8 9 0\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 2\u003c/h3\u003e\n\n\u003cpre\u003e3439\u003c/pre\u003e\n\n\u003cbr\u003e\n\n\u003ch3\u003eSample Input 3\u003c/h3\u003e\n\n\u003cpre\u003e0 9 8 7 6 5 4 3 2 1\n1 0 9 8 7 6 5 4 3 2\n2 1 0 9 8 7 6 5 4 3\n3 2 1 0 9 8 7 6 5 4\n4 3 2 1 0 9 8 7 6 5\n5 4 3 2 1 0 9 8 7 6\n6 5 4 3 2 1 0 9 8 7\n7 6 5 4 3 2 1 0 9 8\n8 7 6 5 4 3 2 1 0 9\n9 8 7 6 5 4 3 2 1 0\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 3\u003c/h3\u003e\n\n\u003cpre\u003e9995\u003c/pre\u003e\n\n\u003cbr\u003e\n\n\u003ch3\u003eSample Input 4\u003c/h3\u003e\n\n\u003cpre\u003e0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 4\u003c/h3\u003e\n\n\u003cpre\u003e10000\u003c/pre\u003e\n\n\n\n\n"}}]}