Counting Ugly Expressions

A number is called ugly if it is divisible by at least one of the one-digit primes 2, 3, 5, and 7. So 14 is ugly and 13 is not, and 39 is ugly and 121 is not. The number 0 is ugly. A negative number can be ugly too, for example -14 and -39.

You are given a string of decimal digits, something like this.

123456

You may insert a plus sign or a minus sign between two adjacent digits to build an expression.

1 + 234 - 5 + 6 = 236

The value of this expression is 236, which is ugly.

123 + 4 - 56 = 71

The value of this expression is 71, which is not ugly.

Counting the expressions is easy. Between each two adjacent digits you choose a plus sign, a minus sign, or nothing, so a string of $D$ digits produces $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.

Among the $3^{D-1}$ expressions, count how many evaluate to an ugly number.

The first line contains the number of test cases $N$. Each of the next $N$ lines contains one 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 13 characters long.

For each test case, print one line in this format.

Case #X: Y

Here $X$ is the test case number starting from 1, and $Y$ is the number of expressions whose value is an ugly number.