Googlements (Large)

A googlement of length $L$ is a string of $L$ decimal digits, each between 0 and $L$ inclusive, that contains at least one digit greater than 0. Leading zeroes are allowed. For example, 103 and 001 are valid googlements of length 3. 400 is not valid, because the digit 4 is greater than the length 3, and 000 is not valid, because it has no digit greater than 0.

A valid googlement can appear in the world at any time, and it later decays into another googlement by a fixed rule. For a googlement of length $L$, count the 1s and write that number down, then count the 2s and write that number to the right of the previous one, and continue in the same way up to the count of $L$s. The string written this way is the googlement after the decay, and its length is still $L$. Some googlements decay into themselves.

For example, suppose 0414 has just appeared. It has one 1, zero 2s, zero 3s and two 4s, so it decays into 1002. That one has one 1, one 2, zero 3s and zero 4s, so it decays into 1100. Then 1100 decays into 2000, 2000 decays into 0100, 0100 decays into 1000, and 1000 decays into itself from then on.

You have observed a googlement $G$. It might have just appeared, or it might be the result of one or more decay steps. Count the googlements that $G$ could have been when it first appeared in the world.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one string $G$ describing a googlement.

Constraints

• $1 \le T \le 100$
• The length of $G$ is between 1 and 9, inclusive.
• Each digit of $G$ is between 0 and the length of $G$, inclusive.
• $G$ contains at least one non-zero digit.

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 googlements the observed one could have been when it first appeared.

In the sample, the first googlement 20 could have been 20 from the start, or it could have decayed from 11. In turn, 11 could have decayed from 12 or from 21, and nothing decays into 12 or 21. That gives four possibilities.

The second googlement 1 is the only googlement of length 1, so the answer is 1.

Nothing decays into the third googlement 123, so 123 itself is the only possibility.