2190. Ugly Numbers

单点时限: 10.0 sec

内存限制: 256 MB

Once upon a time in a strange situation, people called a number ugly if it was divisible by any of the one-digit primes (2, 3, 5 or 7). Thus, 14 is ugly, but 13 is fine. 39 is ugly, but 121 is not. Note that 0 is ugly. Also note that negative numbers can also be ugly; -14 and -39 are examples of such numbers.

One day on your free time, you are gazing at a string of digits, something like:

123456

You are amused by how many possibilities there are if you are allowed to insert plus or minus signs between the digits. For example you can make

1 + 234 - 5 + 6 = 236 which is ugly.

Or 123 + 4 - 56 = 71 which is not ugly.

It is easy to count the number of different ways you can play with the digits: Between each two adjacent digits you may choose put a plus sign, a minus sign, or nothing. Therefore, if you start with D digits there are 3^(D-1) expressions you can make.

Note that it is fine to have leading zeros for a number. If the string is “01023”, then “01023”, “0+1-02+3” and “01-023” are legal expressions.

Your task is simple: Among the 3^(D-1) expressions, count how many of them evaluate to an ugly number.

输入格式

The first line of the input file contains the number of cases, N. Each test case will be a single line containing a non-empty string of decimal digits.

Each string is no more than 40 characters long.

输出格式

For each test case, you should output a line

Case #X: Y

where X is the case number, starting from 1, and Y is the number of expressions that evaluate to an ugly number.

样例

Input
4
1
9
011
12345
Output
Case #1: 0
Case #2: 1
Case #3: 6
Case #4: 64

1 人解决,11 人已尝试。

1 份提交通过,共有 30 份提交。

9.9 EMB 奖励。

创建: 15 年,10 月前.

修改: 6 年,9 月前.

最后提交: 9 年,8 月前.

来源: GCJ 2008

题目标签