Bạn được cho một chuỗi gồm các chữ cái tiếng Anh in hoa. Bạn có thể đánh dấu một số lượng tùy ý các chữ cái (có thể là tất cả hoặc không chữ nào). Các chữ cái được đánh dấu không nhất thiết phải liên tiếp. Sau đó, một chuỗi mới được tạo ra bằng cách xử lý các chữ cái từ trái sang phải: chữ cái không được đánh dấu được nối vào chuỗi mới một lần, còn chữ cái được đánh dấu được nối vào hai lần.

Ví dụ, nếu chuỗi ban đầu là HELLOWORLD, bạn có thể đánh dấu H, chữ L đầu tiên và cuối cùng, cùng chữ O cuối cùng để thu được

HHELLLOWOORLLD, tức HHELLLOWOORLLD.

Tương tự, nếu không đánh dấu chữ nào, bạn thu được HELLOWORLD; nếu đánh dấu tất cả các chữ cái, bạn thu được HHEELLLLOOWWOORRLLDD. Lưu ý rằng mỗi lần xuất hiện của cùng một chữ cái có thể được đánh dấu độc lập.

Với một chuỗi cho trước, tùy vào cách chọn các chữ cái để đánh dấu, ta có thể thu được nhiều chuỗi khác nhau. Trong tất cả các chuỗi ấy, hãy in ra chuỗi đứng đầu tiên theo thứ tự bảng chữ cái (còn gọi là thứ tự từ điển).

Lưu ý: Chuỗi \(s\) đứng trước một chuỗi khác \(t\) theo thứ tự bảng chữ cái nếu \(s\) là tiền tố của \(t\), hoặc nếu tại vị trí đầu tiên mà \(s\) và \(t\) khác nhau, chữ cái trong \(s\) đứng trước chữ cái trong \(t\) trong bảng chữ cái. Ví dụ, các chuỗi sau đang ở đúng thứ tự bảng chữ cái: CODE, HELLO, HI, HIM, HOME, JAM.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(\mathbf{T}\). Tiếp theo là \(\mathbf{T}\) bộ test. Mỗi bộ test được mô tả trên một dòng duy nhất chứa chuỗi \(\mathbf{S}\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo định dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là chuỗi đứng đầu tiên theo thứ tự bảng chữ cái trong tập các chuỗi có thể được tạo từ \(\mathbf{S}\) bằng quy trình đã mô tả.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• Mỗi ký tự của \(\mathbf{S}\) là một chữ cái tiếng Anh in hoa.

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(1 \le |\mathbf{S}| \le 10\).
• Test Set 2 (phán quyết ẩn): \(1 \le |\mathbf{S}| \le 100\).

Đ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ụ

3
PEEL
AAAAAAAAAA
CODEJAMDAY

Case #1: PEEEEL
Case #2: AAAAAAAAAA
Case #3: CCODDEEJAAMDAAY

Nguồn

Google Code Jam 2022, Vòng 1A, bài Double or One Thing.

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