Сіз тұратын шағын қала әлеуметтік сақтандыру нөмірлерінің (SSN) жаңа жүйесін енгізуді жоспарлап отыр. Әрбір азамат бес таңбалы SSN арқылы сәйкестендіріледі. Оның алғашқы төрт цифры базалық ID нөмірін (0000–9999) білдіреді, ал соңғы бір цифры — қателерді анықтауға арналған бақылау цифры.

Бақылау цифрларын есептеу үшін қала билігі амал кестесін қолдануды ұйғарды. Амал кестесі — диагональдық элементтерінің барлығы $0$-ге тең ондық цифрлардан тұратын $10 \times 10$ өлшемді кесте. Төменде амал кестесінің екі мысалы келтірілген.

1-амал кестесі

2-амал кестесі

Амал кестесін пайдалана отырып, төрт таңбалы $abcd$ базалық ID нөмірі үшін $e$ бақылау цифры келесі формула бойынша есептеледі. Мұндағы $i \otimes j$ кестенің $i$-жолы мен $j$-бағанындағы элементін білдіреді.

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

Мысалы, 1-амал кестесін қолданғанда $abcd = 2016$ базалық ID нөмірі үшін $e$ бақылау цифры келесі түрде есептеледі.

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

Сонымен, SSN нөмірі — $20166$.

Бақылау цифры қолданылатын амал кестесіне тәуелді екеніне назар аударыңыз. 2-амал кестесін қолдансақ, дәл сол $2016$ базалық ID нөмірі үшін $e = 3$ болады да, толық SSN нөмірі $20163$ болып шығады.

$$\begin{array}{c} \begin{aligned} 2016 & \\ \Downarrow & \; \text{+2-амал кестесі бойынша бақылау цифры} \\ 20163 & \\ \Downarrow & \; \text{адами қателер} \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{Бір цифрды өзгерту}} \\[10pt] \overbrace{\mathbf{02}163 \quad 2\mathbf{10}63 \quad 20\mathbf{61}3 \quad 201\mathbf{36}}^{\text{Көршілес екі цифрдың орнын ауыстыру}} \end{array}} \end{array}$$

Бақылау цифрын қосудың мақсаты — SSN нөмірлерін жазу немесе теру кезіндегі адами қателерді анықтау. Төмендегі check функциясы кейбір адами қателерді анықтай алады. Бес таңбалы $abcde$ саны үшін check функциясы былайша анықталады.

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

Екінші жағынан, check қайтарған нөлден өзге мән берілген санның дұрыс SSN бола алмайтынын көрсетеді. Қолданылатын амал кестесіне байланысты check функциясы қате SSN үшін де $0$ қайтаруы мүмкін екенін ескеріңіз. Қателердің қандай түрлері анықталатыны қолданылатын амал кестесіне байланысты; кесте қателерді анықтау сапасын айқындайды.

Қала әкімшілігі цифрлар тізбегінде жиі кездесетін адами қателердің екі түрін анықтағысы келеді: B.1-суретте көрсетілгендей, бір ғана цифрды өзгерту және көршілес екі цифрдың орнын ауыстыру.

Егер амал кестесі төрт таңбалы 0000–9999 базалық ID нөмірлерінен құралған барлық SSN нөмірлерінде осы екі түрдегі жиі кездесетін қателердің барлығын анықтай алса, ол жақсы деп аталады. Базалық ID-дің төрт цифрындағы қателер сияқты, бақылау цифрындағы қателер де анықталуы тиіс екеніне назар аударыңыз. Мысалы, 1-амал кестесі жақсы. Ал 2-амал кестесі жақсы емес, өйткені дұрыс $20163$ SSN нөмірінің 3-ші және 4-ші цифрларының орнын ауыстыру арқылы алынған $20613$ саны үшін $\operatorname{check}(20613)$ мәні $0$-ге тең. Іс жүзінде, $10000$ базалық ID нөмірінің ішінде 2-амал кестесі бақандай $3439$ базалық ID нөмірі үшін бір немесе бірнеше жиі кездесетін қатені анықтай алмайды.

Берілген амал кестесі үшін оның бір немесе бірнеше жиі кездесетін қатені анықтай алмайтын базалық 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