Małe miasto, w którym mieszkasz, planuje wprowadzić nowy system numerów ubezpieczenia społecznego (SSN). Każdy obywatel będzie identyfikowany przez pięciocyfrowy SSN. Pierwsze cztery cyfry oznaczają podstawowy numer ID (0000–9999), a ostatnia jest cyfrą kontrolną do wykrywania błędów.

Do obliczania cyfr kontrolnych miasto postanowiło użyć tablicy działania. Jest to tablica $10\times10$ cyfr dziesiętnych, której wszystkie elementy na przekątnej są równe $0$. Poniżej pokazano dwa przykłady.

Tablica działania 1

Tablica działania 2

Przy użyciu tablicy działania cyfra kontrolna $e$ dla czterocyfrowego podstawowego numeru ID $abcd$ jest obliczana według poniższego wzoru. Tutaj $i\otimes j$ oznacza element tablicy w wierszu $i$ i kolumnie $j$.

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

Na przykład przy użyciu tablicy działania 1 cyfra kontrolna $e$ dla podstawowego numeru ID $abcd=2016$ jest obliczana następująco.

$$\begin{aligned}e&=(((0\otimes2)\otimes0)\otimes1)\otimes6\\&=((1\otimes0)\otimes1)\otimes6\\&=(7\otimes1)\otimes6\\&=9\otimes6\\&=6\end{aligned}$$

Zatem SSN wynosi 20166.

Zwróć uwagę, że cyfra kontrolna zależy od użytej tablicy działania. Przy tablicy 2 dla tego samego podstawowego numeru ID 2016 mamy $e=3$, a cały SSN wynosi 20163.

Rysunek B.1. Dwa rodzaje typowych błędów ludzkich

Celem dodania cyfry kontrolnej jest wykrywanie ludzkich błędów podczas pisania lub wpisywania SSN. Poniższa funkcja kontrolna może wykrywać pewne błędy ludzkie. Dla pięciocyfrowego numeru $abcde$ definiujemy ją następująco.

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

Funkcja zwraca $0$ dla poprawnego SSN. Dzieje się tak, ponieważ każdy element na przekątnej tablicy działania jest równy $0$, a dla poprawnego SSN mamy $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.$$

Z drugiej strony niezerowa wartość zwrócona przez $\operatorname{check}$ wskazuje, że dany numer nie może być poprawnym SSN. W zależności od użytej tablicy funkcja może zwrócić $0$ dla niepoprawnego SSN. Rodzaje wykrywanych błędów zależą od tablicy działania; to tablica decyduje o jakości wykrywania błędów.

Władze miasta chcą wykrywać dwa rodzaje typowych błędów ludzkich w ciągach cyfr: zmianę pojedynczej cyfry i zamianę dwóch sąsiednich cyfr, jak pokazano na rysunku B.1.

Tablica działania jest dobra, jeśli wykrywa wszystkie typowe błędy obu rodzajów dla wszystkich SSN utworzonych z czterocyfrowych podstawowych numerów ID 0000–9999. Należy wykrywać błędy zarówno w cyfrze kontrolnej, jak i w czterech cyfrach podstawowego ID. Na przykład tablica 1 jest dobra. Tablica 2 nie jest dobra, ponieważ dla 20613, otrzymanego przez zamianę trzeciej i czwartej cyfry poprawnego SSN 20163, $\operatorname{check}(20613)=0$. W rzeczywistości spośród 10000 podstawowych numerów ID tablica 2 nie wykrywa co najmniej jednego typowego błędu dla aż 3439 numerów.

Mając tablicę działania, oceń jej jakość, licząc podstawowe numery ID, dla których nie wykrywa ona co najmniej jednego typowego błędu.

Wejście

Wejście składa się z jednego przypadku testowego w następującym formacie.

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

Wejście opisuje tablicę działania, gdzie $x_{ij}$ jest cyfrą dziesiętną w wierszu $i$ i kolumnie $j$. Każdy wiersz wejścia odpowiada wierszowi tablicy, w którym elementy są oddzielone pojedynczą spacją. Elementy na przekątnej $x_{ii}$ ($i=0,\ldots,9$) są zawsze równe $0$.

Wyjście

Wypisz liczbę podstawowych numerów ID, dla których dana tablica nie wykrywa co najmniej jednego typowego błędu ludzkiego.

Przykład

Wejście 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

Wyjście 1

0

Wejście 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

Wyjście 2

3439

Wejście 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

Wyjście 3

9995

Wejście 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

Wyjście 4

10000