Bạn đang dự khán trận đấu quan trọng nhất lịch sử thể thao: Oceania Coders gặp Eurasia Jammers trong chung kết thế giới Centrifugal Bumble-Puppy. Vì thiếu ngủ trong lúc mong chờ, bạn đã ngủ quên giữa trận!

Bảng điểm hiện hiển thị cả hai tỷ số, có thể có một hoặc nhiều số 0 ở đầu vì bảng dùng số chữ số cố định. Trong lúc bạn ngủ, những cú bóng mạnh làm hỏng một số đèn, nên một hoặc nhiều chữ số ở một hoặc cả hai tỷ số không còn hiển thị.

Bạn thấy trận đấu sít sao hấp dẫn hơn và muốn hình dung hai tỷ số gần nhau nhất có thể. Hãy điền mọi chữ số thiếu để tối thiểu hóa hiệu tuyệt đối giữa hai tỷ số. Nếu có nhiều cách cùng đạt hiệu nhỏ nhất, chọn cách làm tỷ số Coders nhỏ nhất. Nếu vẫn còn nhiều cách, chọn cách làm tỷ số Jammers nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ test gồm một dòng có hai chuỗi không rỗng \(C\) và \(J\) cùng độ dài, chỉ gồm chữ số thập phân và dấu ?, biểu diễn hai tỷ số đang thấy. Mỗi bộ test có ít nhất một dấu ?.

Dữ liệu ra

Với mỗi bộ test, in Case #x: c j, trong đó \(x\) bắt đầu từ 1; \(c\) và \(j\) lần lượt là \(C\) và \(J\) sau khi thay dấu ? bằng chữ số sao cho \(|c-j|\) nhỏ nhất. Nếu hòa, ưu tiên \(c\) nhỏ nhất, rồi \(j\) nhỏ nhất.

Ràng buộc

• \(1\le T\le200\).
• \(C\) và \(J\) có cùng độ dài.

Phân nhóm

• Test Set 1 (Visible): \(1\le |C|=|J|\le3\).
• Test Set 2 (Hidden): \(1\le |C|=|J|\le18\).

Đ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
1? 2?
?2? ??3
? ?
?5 ?0

Case #1: 19 20
Case #2: 023 023
Case #3: 0 0
Case #4: 05 00

Nguồn

Google Code Jam 2016, Vòng 1B, bài Close Match.

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