เมืองเล็กๆ ที่คุณอาศัยอยู่มีแผนจะนำระบบหมายเลขประกันสังคม (SSN) แบบใหม่มาใช้ พลเมืองแต่ละคนจะถูกระบุตัวตนด้วยหมายเลข SSN ห้าหลัก โดยสี่หลักแรกระบุหมายเลข ID พื้นฐาน (0000–9999) และหลักสุดท้ายหนึ่งหลักคือเลขโดดตรวจสอบสำหรับตรวจหาข้อผิดพลาด

ในการคำนวณเลขโดดตรวจสอบ ทางเมืองได้ตัดสินใจใช้ตารางการดำเนินการ ตารางการดำเนินการคือตารางขนาด $10 \times 10$ ของเลขโดดฐานสิบซึ่งสมาชิกในแนวทแยงมุมหลักทั้งหมดเป็น $0$ ด้านล่างนี้คือตัวอย่างตารางการดำเนินการสองตาราง

ตารางการดำเนินการ 1

ตารางการดำเนินการ 2

เมื่อใช้ตารางการดำเนินการ เลขโดดตรวจสอบ $e$ สำหรับหมายเลข ID พื้นฐานสี่หลัก $abcd$ จะคำนวณโดยใช้สูตรต่อไปนี้ ในที่นี้ $i \otimes j$ แทนสมาชิกของตารางในแถวที่ $i$ และคอลัมน์ที่ $j$

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

ตัวอย่างเช่น เมื่อใช้ตารางการดำเนินการ 1 เลขโดดตรวจสอบ $e$ สำหรับหมายเลข ID พื้นฐาน $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$ สำหรับหมายเลข ID พื้นฐาน $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 ที่สร้างจากหมายเลข ID พื้นฐานสี่หลัก 0000–9999 สังเกตว่าความผิดพลาดที่เกิดกับเลขโดดตรวจสอบรวมถึงที่เกิดกับเลขโดด ID พื้นฐานทั้งสี่หลักจะต้องถูกตรวจพบได้ ตัวอย่างเช่น ตารางการดำเนินการ 1 เป็นตารางที่ดี ส่วนตารางการดำเนินการ 2 ไม่ดี เพราะสำหรับ $20613$ ซึ่งเป็นหมายเลขที่ได้จากการสลับเลขโดดหลักที่ 3 และหลักที่ 4 ของหมายเลข SSN ที่ถูกต้อง $20163$ ค่า $\operatorname{check}(20613)$ เป็น $0$ อันที่จริง ในบรรดาหมายเลข ID พื้นฐาน $10000$ หมายเลข ตารางการดำเนินการ 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