Description

从前在一个奇特的世界里，人们称一个数为“丑数”，如果它能被任意一个一位质数（$2$、$3$、$5$ 或 $7$）整除。因此，$14$ 是丑数，但 $13$ 不是。$39$ 是丑数，但 $121$ 不是。注意，$0$ 也是丑数。同时，负数也可以是丑数，比如 $-14$ 和 $-39$。

有一天，你闲来无事，盯着一串数字，比如：

$123456$

你很好奇，如果允许你在数字之间插入加号或减号，会有多少种可能的表达式。例如，你可以得到：

$1 + 234 - 5 + 6 = 236$

这是一个丑数。或者

$123 + 4 - 56 = 71$

这不是丑数。

计算你可以操作的方式很简单：在每两个相邻数字之间，你可以选择插入加号、减号或什么都不插。因此，如果你有 $D$ 位数字，总共可以构造 $3^{D-1}$ 个表达式。

注意，数字可以有前导零。如果字符串是 "01023"，那么 "01023"、"0+1-02+3" 和 "01-023" 都是合法表达式。

你的任务很简单：在这 $3^{D-1}$ 个表达式中，统计有多少个表达式的结果是丑数。

Input Format

输入的第一行包含一个整数 $N$，表示测试用例的数量。每个测试用例为一行，包含一个非空的十进制数字字符串。

Output Format

对于每个测试用例，输出一行：

Case #X: Y

其中 $X$ 是测试用例编号（从 $1$ 开始），$Y$ 是表达式结果为丑数的表达式个数。

4
1
9
011
12345

Case #1: 0
Case #2: 1
Case #3: 6
Case #4: 64

Hint

限制条件

• $0 \leq N \leq 100$。
• 每个测试用例的字符串非空，仅包含字符 '0' 到 '9'。

小数据集（测试集 1 - 可见）

• 每个字符串长度不超过 $13$。

大数据集（测试集 2 - 隐藏）

• 每个字符串长度不超过 $40$。

由 ChatGPT 4.1 翻译