Ugly Numbers (Large)

A number is called ugly if it is divisible by one of the one-digit primes 2, 3, 5 or 7. So 14 is ugly, but 13 is not. 39 is ugly, but 121 is not. 0 is ugly. Negative numbers can be ugly too. -14 and -39 are examples.

You are given one string of decimal digits, for example:

123456

Between each two adjacent digits you may put a plus sign, a minus sign, or nothing at all. For example, you can build

1 + 234 - 5 + 6 = 236

and the result 236 is ugly. On the other hand,

123 + 4 - 56 = 71

gives 71, which is not ugly.

Counting the expressions is easy. Between each two adjacent digits you pick one of plus, minus, or nothing, so a string of $D$ digits gives $3^{D-1}$ expressions.

A number may have leading zeros. If the string is "01023", then "01023", "0+1-02+3" and "01-023" are all legal expressions.

Count how many of the $3^{D-1}$ expressions evaluate to an ugly number.

The first line contains the number of test cases $N$. Each of the following lines contains one non-empty string of decimal digits.

Limits

• $0 \le N \le 100$
• Each string is non-empty and contains only the characters '0' through '9'.
• Each string is at most 40 characters long.

For each test case, print one line in the form

Case #X: Y

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