Bạn muốn dựng một cặp số nguyên dương. Bạn được cho một danh sách chữ số thập phân và phải dùng mỗi chữ số đúng một lần, nhưng được chọn chữ số nào thuộc số thứ nhất, chữ số nào thuộc số thứ hai.

Bạn cũng được chọn thứ tự chữ số trong mỗi số, ngoại trừ việc chữ số có nghĩa lớn nhất (bên trái nhất) của mỗi số không được là \(0\). Đặc biệt, không thể chọn riêng một chữ số \(0\) làm một số, vì số đó không dương.

Ví dụ, với danh sách \([1,0,2,0,4,3]\), hai cặp hợp lệ là \((200,143)\) và \((3,12400)\). Các cặp sau không hợp lệ:

• \((0102,34)\): có số \(0\) ở đầu;
• \((0,12340)\): có một số không dương;
• \((10,243)\) và \((12300,47)\): danh sách chữ số trong mỗi cặp không đúng bằng danh sách đã cho.

Với danh sách chữ số, hãy tìm hiệu tuyệt đối nhỏ nhất có thể giữa hai số được dựng.

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi dòng tiếp theo chứa một xâu chữ số \(D\); mỗi ký tự của \(D\) là một chữ số bắt buộc phải dùng.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(x\) là số thứ tự (bắt đầu từ \(1\)), còn \(y\) là hiệu tuyệt đối nhỏ nhất giữa hai số được dựng từ \(D\) theo các quy tắc trên.

Ràng buộc

• \(1\le T\le100\).
• Mỗi ký tự của \(D\) là một chữ số thập phân.
• Ít nhất hai ký tự của \(D\) khác 0.

Phân nhóm

• Test Set 1 (Visible Verdict): \(2\le |D|\le8\).
• Test Set 2 (Visible Verdict): \(2\le |D|\le36\).

Đ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
1234
0011
07080
0899

Case #1: 7
Case #2: 0
Case #3: 620
Case #4: 1

Nguồn

Google Code Jam 2021, Vòng 3, bài Build-A-Pair.

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