cho.sh

Counting Ugly Expressions

Insert +, -, or nothing between adjacent digits of a digit string, count how many of the 3^(D-1) expressions evaluate to a number divisible by 2, 3, 5, or 7.

Medium4Brute forceRecursionNumber theoryImplementationInterviewNo attempts yetTime limit5sMemory limit512 MB

Problem

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 DD digits produces 3D−13^{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 3D−13^{D-1} expressions, count how many evaluate to an ugly number.

Input

The first line contains the number of test cases NN. Each of the next NN lines contains one string of decimal digits.

Limits

  • 0≤N≤1000 \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.

Output

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

Case #X: Y

Here XX is the test case number starting from 1, and YY is the number of expressions whose value is an ugly number.