당신이 사는 작은 도시는 새로운 사회 보장 번호(SSN) 시스템을 도입하려고 한다. 각 시민은 다섯 자리 SSN으로 식별된다. 앞의 네 자리는 기본 ID 번호(0000–9999)를 나타내고, 마지막 한 자리는 오류를 검출하는 검사 숫자이다.
검사 숫자를 계산하기 위해 도시는 연산표를 사용하기로 했다. 연산표는 대각 원소가 모두 $0$인 십진 숫자의 $10\times10$ 표이다. 아래는 두 연산표의 예시이다.
연산표 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$ |
연산표를 사용하면 네 자리 기본 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. 흔한 사람의 실수 두 종류
검사 숫자를 추가하는 목적은 SSN을 쓰거나 입력할 때의 사람의 실수를 검출하는 것이다. 다음 검사 함수는 일부 사람의 실수를 검출할 수 있다. 다섯 자리 수 $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에 나타난 것처럼 숫자열에서 흔히 발생하는 두 종류의 사람의 실수, 즉 한 숫자를 바꾸는 것과 인접한 두 숫자를 맞바꾸는 것을 검출하려고 한다.
네 자리 기본 ID 번호 0000–9999로 만든 모든 SSN에서 두 종류의 흔한 실수를 모두 검출할 수 있으면 연산표가 좋다고 한다. 기본 ID 네 자리뿐 아니라 검사 숫자에서의 오류도 검출해야 한다. 예를 들어 연산표 1은 좋다. 연산표 2는 좋지 않은데, 올바른 SSN 20163의 세 번째와 네 번째 숫자를 맞바꿔 얻은 수 20613에 대해 $\operatorname{check}(20613)=0$이기 때문이다. 실제로 10000개의 기본 ID 번호 중 연산표 2는 무려 3439개에서 하나 이상의 흔한 실수를 검출하지 못한다.
연산표가 주어지면, 그 표가 하나 이상의 흔한 실수를 검출하지 못하는 기본 ID 번호의 개수를 세어 얼마나 좋은 표인지 판별하라.
입력
입력은 다음 형식의 단일 테스트 케이스로 구성된다.
$$\begin{array}{cccc}x_{00}&x_{01}&\cdots&x_{09}\\\vdots\\x_{90}&x_{91}&\cdots&x_{99}\end{array}$$
입력은 연산표를 설명하며, $x_{ij}$는 $i$행 $j$열의 십진 숫자이다. 각 줄은 표의 한 행에 대응하고 원소는 공백 하나로 구분된다. 대각 원소 $x_{ii}$ ($i=0,\ldots,9$)는 항상 $0$이다.
출력
주어진 표가 하나 이상의 흔한 사람의 실수를 검출하지 못하는 기본 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