Kota kecil tempat tinggal Anda berencana memperkenalkan sistem nomor jaminan sosial (SSN) yang baru. Setiap warga akan diidentifikasi dengan SSN lima digit. Empat digit pertamanya menunjukkan nomor ID dasar (0000–9999) dan satu digit terakhir adalah digit pemeriksa untuk mendeteksi kesalahan.

Untuk menghitung digit pemeriksa, pemerintah kota memutuskan untuk menggunakan sebuah tabel operasi. Tabel operasi adalah tabel berukuran $10 \times 10$ berisi digit desimal yang semua elemen diagonalnya bernilai $0$. Di bawah ini adalah dua contoh tabel operasi.

Tabel Operasi 1

Tabel Operasi 2

Dengan menggunakan sebuah tabel operasi, digit pemeriksa $e$ untuk nomor ID dasar empat digit $abcd$ dihitung menggunakan rumus berikut. Di sini, $i \otimes j$ menyatakan elemen tabel pada baris $i$ dan kolom $j$.

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

Sebagai contoh, dengan menggunakan Tabel Operasi 1, digit pemeriksa $e$ untuk nomor ID dasar $abcd = 2016$ dihitung dengan cara berikut.

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

Dengan demikian, SSN-nya adalah $20166$.

Perhatikan bahwa digit pemeriksa bergantung pada tabel operasi yang digunakan. Dengan Tabel Operasi 2, kita memperoleh $e = 3$ untuk nomor ID dasar $2016$ yang sama, dan keseluruhan SSN akan menjadi $20163$.

$$\begin{array}{c} \begin{aligned} 2016 & \\ \Downarrow & \; \text{+digit pemeriksa menggunakan Tabel Operasi 2} \\ 20163 & \\ \Downarrow & \; \text{kesalahan manusia} \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{Mengubah satu digit tunggal}} \\[10pt] \overbrace{\mathbf{02}163 \quad 2\mathbf{10}63 \quad 20\mathbf{61}3 \quad 201\mathbf{36}}^{\text{Menukar dua digit bersebelahan}} \end{array}} \end{array}$$

Tujuan penambahan digit pemeriksa adalah untuk mendeteksi kesalahan manusia saat menulis atau mengetik SSN. Fungsi check berikut dapat mendeteksi kesalahan manusia tertentu. Untuk bilangan lima digit $abcde$, fungsi check didefinisikan sebagai berikut.

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

Fungsi ini mengembalikan $0$ untuk SSN yang benar. Hal ini karena setiap elemen diagonal pada tabel operasi bernilai $0$ dan untuk SSN yang benar berlaku $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.$$

Di sisi lain, nilai tak-nol yang dikembalikan oleh check menunjukkan bahwa nomor yang diberikan tidak mungkin merupakan SSN yang benar. Perhatikan bahwa bergantung pada tabel operasi yang digunakan, fungsi check dapat mengembalikan $0$ untuk SSN yang salah. Jenis kesalahan yang terdeteksi bergantung pada tabel operasi yang digunakan; tabel tersebut menentukan kualitas pendeteksian kesalahan.

Pemerintah kota ingin mendeteksi dua jenis kesalahan manusia yang umum pada barisan digit: mengubah satu digit tunggal dan menukar dua digit yang bersebelahan, sebagaimana ditunjukkan pada Gambar B.1.

Sebuah tabel operasi dikatakan baik jika tabel tersebut dapat mendeteksi semua kesalahan umum dari kedua jenis tersebut pada semua SSN yang dibentuk dari nomor ID dasar empat digit 0000–9999. Perhatikan bahwa kesalahan pada digit pemeriksa maupun pada keempat digit ID dasar harus terdeteksi. Sebagai contoh, Tabel Operasi 1 adalah baik. Tabel Operasi 2 tidak baik karena, untuk $20613$, yaitu nomor yang diperoleh dengan menukar digit ke-3 dan ke-4 dari SSN yang benar $20163$, nilai $\operatorname{check}(20613)$ adalah $0$. Bahkan, di antara $10000$ nomor ID dasar, Tabel Operasi 2 tidak dapat mendeteksi satu atau lebih kesalahan umum pada sebanyak $3439$ nomor ID dasar.

Diberikan sebuah tabel operasi, tentukan seberapa baik tabel tersebut dengan menghitung banyaknya nomor ID dasar yang untuknya tabel yang diberikan tidak dapat mendeteksi satu atau lebih kesalahan umum.

Masukan

Masukan terdiri atas satu kasus uji dengan format berikut.

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

Masukan mendeskripsikan sebuah tabel operasi dengan $x_{ij}$ merupakan digit desimal pada baris $i$ dan kolom $j$. Setiap baris pada masukan bersesuaian dengan satu baris tabel, yang elemen-elemennya dipisahkan oleh satu spasi tunggal. Elemen diagonal $x_{ii}$ ($i = 0, \ldots, 9$) selalu bernilai $0$.

Keluaran

Keluarkan banyaknya nomor ID dasar yang untuknya tabel yang diberikan tidak dapat mendeteksi satu atau lebih kesalahan manusia yang umum.

Contoh

Masukan 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

Keluaran 1

0

Masukan 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

Keluaran 2

3439

Masukan 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

Keluaran 3

9995

Masukan 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

Keluaran 4

10000