Seconds Before the War

In the year 2100 aliens reached Earth. They left a message written in a language nobody can read, and next to it a row of symbols. The row of symbols spells out a number, and that number is how many seconds remain before a war begins.

Nobody knows what a single symbol means. Each symbol stands for one digit, but which digit hides behind which symbol is unknown, and so is the base the aliens write in. If they wrote ab2ac999, they may have meant 31536000 in base 10, which is exactly one year, or 12314555 in base 6, which is 398951 seconds, a little over four and a half days.

Three facts are certain. The number is positive, the aliens never begin a number with a zero, and they do not write in base 1.

Find the smallest number of seconds the message can stand for.

The first line has one integer $T$, the number of test cases. Each of the next $T$ lines holds one message on a line by itself. A message uses only the characters a to z and 0 to 9, with no spaces and no punctuation. The test cases are independent, so two messages may use different bases and may give different digits to the same symbol.

• $1 \le T \le 100$
• The length of each message is at least $1$ and at most $60$
• The answer never exceeds $10^{18}$

For each test case, print one line in this format:

Case #X: V

$X$ is the case number starting from 1, and $V$ is the smallest number of seconds before the war begins.