Bạn vừa làm quen một người bạn mới tại hội nghị câu đố quốc tế và hỏi cách giữ liên lạc. Hôm sau, bạn thấy mảnh giấy sau được luồn dưới cửa phòng khách sạn:

“Xin chào, người bạn mới! Tôi đã thay mỗi chữ số trong số điện thoại bằng cách viết nó bằng chữ tiếng Anh in hoa (ZERO, ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE tương ứng các chữ số từ 0 đến 9), rồi xáo trộn tất cả các chữ cái để tạo chuỗi \(S\). Bạn phải dùng \(S\) để tìm số điện thoại có bao nhiêu chữ số và chúng là gì; tôi chỉ tiết lộ rằng các chữ số trong số điện thoại ở thứ tự không giảm. Hãy gọi cho tôi... nếu bạn làm được!”

Bạn muốn gọi để nói rằng đây là cách đưa số điện thoại thật khó chịu, nhưng phải tìm được số thì mới gọi được. Số điện thoại là gì?

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ test gồm một dòng chứa chuỗi \(S\) các chữ cái tiếng Anh in hoa.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là chuỗi chữ số của số điện thoại.

Ràng buộc

• \(1\le T\le100\).
• Bảo đảm tồn tại duy nhất một đáp án.

Phân nhóm

• Test Set 1 (Visible): \(3\le |S|\le20\).
• Test Set 2 (Hidden): \(3\le |S|\le2000\).

Đ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
OZONETOWER
WEIGHFOXTOURIST
OURNEONFOE
ETHER

Case #1: 012
Case #2: 2468
Case #3: 114
Case #4: 3

Nguồn

Google Code Jam 2016, Vòng 1B, bài Getting the Digits.

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