如果一个数能被任何一位质数（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}$ 个表达式中，计算有多少个表达式的计算结果是丑数。

样例

输入格式 1

4
1
9
011
12345

输出格式 1

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