Description

化学家研究元素周期表中的元素，而在 Code Jam，我们一直在用先进的数字粉碎机研究 googlement。googlement 是一种可以用最多九位数字表示的物质。长度为 $L$ 的 googlement 只能包含 $0$ 到 $L$（包含 $L$）之间的十进制数字，并且必须至少包含一个大于 $0$ 的数字。允许前导零。例如，$103$ 和 $001$ 是长度为 $3$ 的合法 googlement。$400$（包含了一个大于 googlement 长度 $3$ 的数字 $4$）和 $000$（没有任何大于 $0$ 的数字）都不是合法的 googlement。

任何合法的 googlement 都可能在世界上随时出现，但最终会以确定性的方式衰变为另一个 googlement。具体规则如下：对于长度为 $L$ 的 googlement，统计其中 $1$ 的个数（可能为 $0$），并写下该值，然后统计 $2$ 的个数并写在前一个数字的右边，依此类推，直到统计并写下 $L$ 的个数。这样生成的新字符串就是新的 googlement，其长度同样为 $L$。有时 googlement 甚至可能衰变为自身！

例如，假设 googlement $0414$ 刚刚出现。它包含一个 $1$，零个 $2$，零个 $3$，两个 $4$，因此会衰变为 googlement $1002$。$1002$ 包含一个 $1$，一个 $2$，零个 $3$，零个 $4$，因此会衰变为 $1100$，接着衰变为 $2000$，再衰变为 $0100$，再衰变为 $1000$，最后会不断地衰变为自身。

你刚刚观察到了一个 googlement $G$。这个 googlement 可能是刚刚在世界上出现的，也可能是经过一次或多次衰变后的结果。请问，$G$ 最初在世界上出现时可能是哪几个不同的 googlement？请输出所有可能的数量。

Input Format

第一行包含测试用例的数量 $T$。接下来有 $T$ 组测试数据，每组一行，包含一个字符串 $G$，表示一个 googlement。

Output Format

对于每组测试数据，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是观察到的 googlement 最初可能的不同 googlement 的数量。

3
20
1
123

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

Hint

样例解释

样例 $1$ 中，googlement 最初可能是 $20$，也可能是由 $11$ 衰变而来，而 $11$ 又可能由 $12$ 或 $21$ 衰变而来。这两者都不可能是其他 googlement 衰变的结果。所以总共有四种可能。

样例 $2$ 中，googlement 必须最初就是 $1$，这是唯一可能的长度为 $1$ 的 googlement。

样例 $3$ 中，googlement 必须最初就是 $123$，没有其他 googlement 能够衰变为它。

数据范围

• $1 \leq T \leq 100$。
• $G$ 中每一位都是 $0$ 到 $G$ 的长度之间的十进制数字。
• $G$ 至少包含一个非零数字。

小数据集（3 分，测试点 1 - 可见）

• 时间限制：20 5 秒。
• $1 \leq G$ 的长度 $\leq 5$。

大数据集（10 分，测试点 2 - 隐藏）

• 时间限制：60 15 秒。
• $1 \leq G$ 的长度 $\leq 9$。

由 ChatGPT 4.1 翻译