化学家们研究元素周期表，但在 Code Jam，我们一直使用我们的高级数字粉碎机来研究“谷歌元素”（googlements）。谷歌元素是一种可以用最多九位数字的字符串表示的物质。长度为 $L$ 的谷歌元素必须仅包含 $0$ 到 $L$（含 $0$ 和 $L$）之间的十进制数字，且必须至少包含一个大于 $0$ 的数字。允许前导零。例如，$103$ 和 $001$ 是长度为 $3$ 的有效谷歌元素。而 $400$（包含一个大于谷歌元素长度 $3$ 的数字 $4$）和 $000$（不包含任何大于 $0$ 的数字）则不是。

任何有效的谷歌元素都可能在任何时候出现在世界上，但它最终会以确定的方式衰变为另一个谷歌元素，过程如下：对于长度为 $L$ 的谷歌元素，统计其中 $1$ 的个数（可能是 $0$），写下该值；然后统计其中 $2$ 的个数（可能是 $0$），将该值写在前一个值的右侧；以此类推，直到最后统计并写下 $L$ 的个数。以这种方式生成的新字符串代表新的谷歌元素，它也将具有长度 $L$。甚至可能出现谷歌元素衰变为自身的情况！

例如，假设刚刚出现了谷歌元素 $0414$。它包含一个 $1$，零个 $2$，零个 $3$，以及两个 $4$，因此它将衰变为谷歌元素 $1002$。它包含一个 $1$，一个 $2$，零个 $3$，以及零个 $4$，因此它将衰变为 $1100$，接着衰变为 $2000$，再衰变为 $0100$，再衰变为 $1000$，最后将持续衰变为自身。

你刚刚观察到了一个谷歌元素 $G$。这个谷歌元素可能是刚刚出现在世界上的，也可能是经过一次或多次衰变步骤后的结果。当它最初出现在世界上时，它可能是哪些谷歌元素？请计算所有可能的谷歌元素总数。

输入格式

第一行包含测试用例的数量 $T$。接下来的 $T$ 行，每行包含一个字符串 $G$，代表一个谷歌元素。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是观察到的谷歌元素在最初出现在世界上时，所有可能的谷歌元素数量。

数据范围

内存限制：1 GB。 $1 \le T \le 100$。 $G$ 中的每个数字都是 $0$ 到 $G$ 的长度之间的十进制数字。 $G$ 至少包含一个非零数字。

子任务 1 时间限制：10 秒。 $1 \le$ $G$ 的长度 $\le 5$。

子任务 2 时间限制：30 秒。 $1 \le$ $G$ 的长度 $\le 9$。

样例

样例输入 1

3
20
1
123

样例输出 1

Case #1: 4
Case #2: 1
Case #3: 1

说明

在样例 #1 中，该谷歌元素最初可能是 $20$，或者它可能由 $11$ 衰变而来，而 $11$ 本身可能由 $12$ 或 $21$ 衰变而来。后两者都不可能是衰变的产物。因此总共有四种可能性。

在样例 #2 中，该谷歌元素最初一定是 $1$，这是长度为 $1$ 的唯一可能的谷歌元素。

在样例 #3 中，该谷歌元素一定是 $123$；没有其他谷歌元素能衰变为它。