P13464 [GCJ 2008 #1C] Ugly Numbers

从前在一个奇特的世界里，人们称一个数为“丑数”，如果它能被任意一个一位质数（$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}$ 个表达式中，统计有多少个表达式的结果是丑数。

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

对于每个测试用例，输出一行： Case #X: Y 其中 $X$ 是测试用例编号（从 $1$ 开始），$Y$ 是表达式结果为丑数的表达式个数。

**限制条件** - $0 \leq N \leq 100$。 - 每个测试用例的字符串非空，仅包含字符 '0' 到 '9'。 **小数据集（测试集 1 - 可见）** - 每个字符串长度不超过 $13$。 **大数据集（测试集 2 - 隐藏）** - 每个字符串长度不超过 $40$。 由 ChatGPT 4.1 翻译