Vào năm 2100, người ngoài hành tinh đến Trái Đất. Họ để lại một thông điệp bằng ngôn ngữ bí ẩn cùng một dãy ký hiệu. Ta kết luận rằng dãy ký hiệu biểu diễn số giây còn lại trước khi chiến tranh bắt đầu.

Mỗi ký hiệu là một chữ số, nhưng ta không biết giá trị của từng ký hiệu hay cơ số họ dùng. Chẳng hạn, ab2ac999 có thể là 31536000 trong hệ 10 (đúng một năm), hoặc 12314555 trong hệ 6 (398951 giây, tức khoảng bốn ngày rưỡi). Ta biết số đó dương, chữ số đầu không phải 0 và cơ số không phải 1.

Hãy tìm số giây nhỏ nhất có thể trước khi chiến tranh bắt đầu.

Dữ liệu vào

Dòng đầu chứa số nguyên \(T\). Mỗi trong \(T\) dòng tiếp theo là một chuỗi chỉ gồm a-z và 0-9, không có dấu cách hay dấu câu. Các test độc lập; cơ số và ý nghĩa ký hiệu có thể khác nhau.

Dữ liệu ra

Với mỗi test, in Case #X: V, trong đó \(X\) đánh số từ 1 và \(V\) là số giây nhỏ nhất.

Ràng buộc

• \(1 \le T \le 100\).
• Đáp án không vượt quá \(10^{18}\).

Phân nhóm

• Nhỏ: độ dài mỗi chuỗi từ 1 đến 9.
• Lớn: độ dài mỗi chuỗi từ 1 đến 60.

Đ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
11001001
cats
zig

Case #1: 201
Case #2: 75
Case #3: 11

Nguồn

Google Code Jam 2009, Vòng 1C, bài All Your Base.

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