Cameron và Jamie sắp chào đón em bé thứ hai. Họ vốn đã phối hợp ăn ý trong vai trò cha mẹ, nhưng lúc này lại bất đồng về một việc vô cùng quan trọng! Cameron muốn đặt cho em bé một cái tên (chuỗi C), còn Jamie lại muốn đặt một cái tên khác (chuỗi J).

Bạn muốn giúp họ tìm một tên thỏa hiệp gần nhất có thể với mong muốn của mỗi người. Bạn cho rằng có thể làm điều này bằng khái niệm khoảng cách chỉnh sửa. Khoảng cách chỉnh sửa giữa hai chuỗi \(S_1\) và \(S_2\) là số phép toán ít nhất cần thực hiện để biến đổi \(S_1\) thành \(S_2\), trong đó các phép toán được phép là:

• Chèn một ký tự vào vị trí bất kỳ trong chuỗi.
• Xóa một ký tự khỏi vị trí bất kỳ trong chuỗi.
• Đổi một ký tự trong chuỗi thành một ký tự bất kỳ khác.

Ví dụ, khoảng cách chỉnh sửa giữa CAMERON và JAMIE là 5. Một cách thực hiện phép biến đổi trong 5 bước là: CAMERON thành JAMERON (đổi), thành JAMIERON (chèn), thành JAMIEON (xóa), thành JAMIEN (xóa), rồi thành JAMIE (xóa). Mọi cách biến đổi CAMERON thành JAMIE đều cần ít nhất từng ấy phép toán.

Để tên thỏa hiệp \(N\) gần nhất có thể với mong muốn ban đầu của cha mẹ, bạn muốn \(N\) là một chuỗi không rỗng sao cho tổng khoảng cách chỉnh sửa giữa C và \(N\) với khoảng cách chỉnh sửa giữa J và \(N\) là nhỏ nhất có thể. Trong tất cả các lựa chọn \(N\) như vậy, để bảo đảm sự thỏa hiệp là công bằng, bạn phải chọn một \(N\) sao cho hiệu tuyệt đối giữa hai khoảng cách chỉnh sửa đó cũng nhỏ nhất có thể. Hãy tìm một tên thỏa hiệp cho Cameron và Jamie.

Dữ liệu vào

Dòng đầu tiên cho biết số lượng bộ test T. Tiếp theo là T bộ test. Mỗi bộ gồm một dòng chứa hai chuỗi C và J, lần lượt là những cái tên Cameron và Jamie đề xuất cho em bé. Mỗi tên chỉ gồm các chữ cái tiếng Anh viết hoa.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là một cái tên đáp ứng các yêu cầu đã nêu. Lưu ý rằng y chỉ được chứa các chữ cái tiếng Anh viết hoa.

Ràng buộc

• \(1 \leq \mathbf{T} \leq 100\).
• \(\mathbf{C} \neq \mathbf{J}\).

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• \(1 \leq |\mathbf{C}| \leq 6\).
• \(1 \leq |\mathbf{J}| \leq 6\).
• Với mọi \(i\), ký tự thứ \(i\) của C là một trong các chữ cái viết hoa X, Y hoặc Z.
• Với mọi \(i\), ký tự thứ \(i\) của J là một trong các chữ cái viết hoa X, Y hoặc Z.

Test Set 2 (Phán quyết ẩn)

• \(1 \leq |\mathbf{C}| \leq 60\).
• \(1 \leq |\mathbf{J}| \leq 60\).
• Với mọi \(i\), ký tự thứ \(i\) của C là một chữ cái tiếng Anh viết hoa.
• Với mọi \(i\), ký tự thứ \(i\) của J là một chữ cái tiếng Anh viết hoa.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
XYZZY ZZYZX
Y Z
YYXXYZ ZYYXXY
XZXZXZ YZ

Case #1: ZZY
Case #2: Z
Case #3: ZYYXXYZ
Case #4: ZYZX

1
GCJ ABC

Nguồn

Google Code Jam 2020, Vòng 3, bài Naming Compromise.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.