Thành phố nhỏ nơi bạn sinh sống dự định áp dụng một hệ thống mã số an sinh xã hội (SSN) mới. Mỗi công dân sẽ được định danh bằng một mã SSN gồm năm chữ số. Bốn chữ số đầu tiên cho biết mã ID cơ sở (0000–9999) và chữ số cuối cùng là chữ số kiểm tra dùng để phát hiện lỗi.

Để tính các chữ số kiểm tra, thành phố quyết định sử dụng một bảng phép toán. Bảng phép toán là một bảng kích thước $10 \times 10$ gồm các chữ số thập phân mà mọi phần tử trên đường chéo chính đều bằng $0$. Dưới đây là hai bảng phép toán ví dụ.

Bảng phép toán 1

Bảng phép toán 2

Sử dụng một bảng phép toán, chữ số kiểm tra $e$ cho mã ID cơ sở bốn chữ số $abcd$ được tính theo công thức sau. Ở đây, $i \otimes j$ ký hiệu phần tử của bảng nằm ở hàng $i$ và cột $j$.

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

Ví dụ, khi sử dụng Bảng phép toán 1, chữ số kiểm tra $e$ cho mã ID cơ sở $abcd = 2016$ được tính theo cách sau.

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

Do đó, mã SSN là $20166$.

Lưu ý rằng chữ số kiểm tra phụ thuộc vào bảng phép toán được sử dụng. Với Bảng phép toán 2, ta có $e = 3$ cho cùng mã ID cơ sở $2016$, và toàn bộ mã SSN sẽ là $20163$.

$$\begin{array}{c} \begin{aligned} 2016 & \\ \Downarrow & \; \text{+chữ số kiểm tra dùng Bảng phép toán 2} \\ 20163 & \\ \Downarrow & \; \text{lỗi con người} \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{Thay đổi một chữ số duy nhất}} \\[10pt] \overbrace{\mathbf{02}163 \quad 2\mathbf{10}63 \quad 20\mathbf{61}3 \quad 201\mathbf{36}}^{\text{Đổi chỗ hai chữ số kề nhau}} \end{array}} \end{array}$$

Mục đích của việc thêm chữ số kiểm tra là phát hiện lỗi của con người khi viết hoặc gõ mã SSN. Hàm check dưới đây có thể phát hiện một số lỗi con người nhất định. Đối với một số gồm năm chữ số $abcde$, hàm check được định nghĩa như sau.

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

Hàm này trả về $0$ đối với một mã SSN đúng. Điều này là do mọi phần tử trên đường chéo chính trong bảng phép toán đều bằng $0$ và với một mã SSN đúng ta có $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.$$

Mặt khác, một giá trị khác không do hàm check trả về cho biết số đã cho không thể là một mã SSN đúng. Lưu ý rằng tùy thuộc vào bảng phép toán được sử dụng, hàm check vẫn có thể trả về $0$ đối với một mã SSN sai. Những loại lỗi nào được phát hiện phụ thuộc vào bảng phép toán được dùng; bảng phép toán quyết định chất lượng phát hiện lỗi.

Chính quyền thành phố muốn phát hiện hai loại lỗi con người phổ biến trên dãy chữ số: thay đổi một chữ số duy nhất và đổi chỗ hai chữ số kề nhau, như được minh họa trong Hình B.1.

Một bảng phép toán được gọi là tốt nếu nó có thể phát hiện tất cả các lỗi phổ biến thuộc cả hai loại trên mọi mã SSN được tạo từ các mã ID cơ sở bốn chữ số 0000–9999. Lưu ý rằng lỗi xảy ra ở chữ số kiểm tra cũng như ở bốn chữ số ID cơ sở đều phải được phát hiện. Ví dụ, Bảng phép toán 1 là tốt. Bảng phép toán 2 không tốt vì với $20613$, là số thu được bằng cách đổi chỗ chữ số thứ 3 và thứ 4 của mã SSN đúng $20163$, giá trị $\operatorname{check}(20613)$ bằng $0$. Thực tế, trong số $10000$ mã ID cơ sở, Bảng phép toán 2 không thể phát hiện một hoặc nhiều lỗi phổ biến cho tới $3439$ mã ID cơ sở.

Cho một bảng phép toán, hãy xác định mức độ tốt của nó bằng cách đếm số lượng mã ID cơ sở mà bảng đã cho không thể phát hiện một hoặc nhiều lỗi phổ biến.

Dữ liệu vào

Dữ liệu vào gồm một bộ kiểm tra duy nhất theo định dạng sau.

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

Dữ liệu vào mô tả một bảng phép toán với $x_{ij}$ là chữ số thập phân ở hàng $i$ và cột $j$. Mỗi dòng tương ứng với một hàng của bảng, trong đó các phần tử được ngăn cách bởi đúng một dấu cách. Các phần tử trên đường chéo chính $x_{ii}$ ($i = 0, \ldots, 9$) luôn bằng $0$.

Dữ liệu ra

In ra số lượng mã ID cơ sở mà bảng đã cho không thể phát hiện một hoặc nhiều lỗi con người phổ biến.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

0

Dữ liệu vào 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

Dữ liệu ra 2

3439

Dữ liệu vào 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

Dữ liệu ra 3

9995

Dữ liệu vào 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

Dữ liệu ra 4

10000