公元 2100 年，外星人来到了地球。他们用一种神秘的语言写下了一条信息，并在旁边写下了一系列符号。我们得出的结论是，这些符号代表一个数字：战争开始前的秒数！

不幸的是，我们不知道每个符号代表什么。我们确定每个符号代表一个数字，但不确定每个数字的具体含义，也不确定外星人使用的是什么进制。例如，如果他们写下 "ab2ac999"，他们可能指的是 10 进制下的 "31536000"（正好一年），也可能指的是 6 进制下的 "12314555"（398951 秒，大约四天半）。我们确定三件事：这个数字是正数；和我们一样，外星人绝不会以 0 开头；他们不使用一进制（base 1）。

你的任务是确定战争开始前可能的最小秒数。

输入格式

输入的第一行包含一个整数 $T$。接下来有 $T$ 组测试数据。每组测试数据占一行，仅包含 'a' 到 'z' 和 '0' 到 '9' 范围内的字符（没有空格和标点符号），代表外星人留下的信息。各测试数据相互独立，可能使用不同的进制，符号的含义也可能不同。

输出格式

对于每组测试数据，按以下格式输出一行：

Case #$X$: $V$

其中 $X$ 是测试数据的编号（从 1 开始），$V$ 是战争开始前的最小秒数。

数据范围

$1 \le T \le 100$ 答案不会超过 $10^{18}$

小数据集（8 分）

$1 \le$ 每行字符串长度 $< 10$

大数据集（15 分）

$1 \le$ 每行字符串长度 $< 61$

样例

样例输入 1

3
11001001
cats
zig

样例输出 1

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