تخطط المدينة الصغيرة التي تعيش فيها لإدخال نظام جديد لأرقام الضمان الاجتماعي (SSN). سيتم تعريف كل مواطن برقم SSN مكوّن من خمسة أرقام. تشير الأرقام الأربعة الأولى منه إلى رقم الهوية الأساسي (0000–9999)، والرقم الأخير هو رقم تحقق لاكتشاف الأخطاء.

لحساب أرقام التحقق، قررت المدينة استخدام جدول عملية. جدول العملية هو جدول أبعاده $10 \times 10$ من الأرقام العشرية جميع عناصر قطره الرئيسي تساوي $0$. وفيما يلي مثالان لجدولي عملية.

جدول العملية 1

جدول العملية 2

باستخدام جدول العملية، يُحسَب رقم التحقق $e$ لرقم هوية أساسي مكوّن من أربعة أرقام $abcd$ وفق الصيغة التالية. هنا يرمز $i \otimes j$ إلى عنصر الجدول الواقع في الصف $i$ والعمود $j$.

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

على سبيل المثال، باستخدام جدول العملية 1، يُحسَب رقم التحقق $e$ لرقم الهوية الأساسي $abcd = 2016$ بالطريقة التالية.

$$\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 نحصل على $e = 3$ لنفس رقم الهوية الأساسي $2016$، ويكون رقم 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$$

تُعيد هذه الدالة القيمة $0$ لرقم SSN الصحيح؛ وذلك لأن كل عنصر قطري في جدول العملية يساوي $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 القيمة $0$ لرقم SSN غير صحيح. تعتمد أنواع الأخطاء المكتشَفة على جدول العملية المستخدم؛ فالجدول هو الذي يحدد جودة اكتشاف الأخطاء.

ترغب سلطات المدينة في اكتشاف نوعين من الأخطاء البشرية الشائعة في متتاليات الأرقام: تغيير رقم واحد، وتبديل رقمين متجاورين، كما هو موضح في الشكل B.1.

يُوصَف جدول العملية بأنه جيد إذا كان قادرًا على اكتشاف جميع الأخطاء الشائعة من هذين النوعين في كل أرقام SSN المنشأة من أرقام الهوية الأساسية ذات الأربعة أرقام 0000–9999. لاحظ أنه ينبغي اكتشاف الأخطاء الواقعة في رقم التحقق وكذلك في الأرقام الأربعة لرقم الهوية الأساسي. على سبيل المثال، جدول العملية 1 جيد. أما جدول العملية 2 فليس جيدًا لأنه بالنسبة للعدد $20613$، وهو عدد ناتج عن تبديل الرقمين الثالث والرابع من رقم SSN الصحيح $20163$، تكون قيمة $\operatorname{check}(20613)$ مساوية لـ $0$. وفي الواقع، من بين $10000$ رقم هوية أساسي، يعجز جدول العملية 2 عن اكتشاف خطأ شائع واحد أو أكثر لما يصل إلى $3439$ رقم هوية أساسي.

بالنظر إلى جدول عملية معطى، حدد مدى جودته عن طريق حساب عدد أرقام الهوية الأساسية التي يعجز الجدول المعطى عن اكتشاف خطأ شائع واحد أو أكثر لها.

الإدخال

يتكون الإدخال من حالة اختبار واحدة بالتنسيق التالي.

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

الإخراج

اطبع عدد أرقام الهوية الأساسية التي يعجز الجدول المعطى عن اكتشاف خطأ بشري شائع واحد أو أكثر لها.

أمثلة

الإدخال 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