题目描述

Chemists work with periodic table elements, but here at Code Jam, we have been using our advanced number smasher to study googlements. A googlement is a substance that can be represented by a string of at most nine digits. A googlement of length $L$ must contain only decimal digits in the range $0$ through $L$, inclusive, and it must contain at least one digit greater than $0$. Leading zeroes are allowed. For example, $103$ and $001$ are valid googlements of length $3$. $400$ (which contains a digit, $4$, greater than the length of the googlement, $3$) and $000$ (which contains no digit greater than 0) are not.

Any valid googlement can appear in the world at any time, but it will eventually decay into another googlement in a deterministic way, as follows. For a googlement of length $L$, count the number of $1$s in the googlement (which could be $0$) and write down that value, then count the number of $2$s in the googlement (which could be $0$) and write down that value to the right of the previous value, and so on, until you finally count and write down the number of $L$s. The new string generated in this way represents the new googlement, and it will also have length $L$. It is even possible for a googlement to decay into itself!

For example, suppose that the googlement $0414$ has just appeared. This has one $1$, zero $2$s, zero $3$s, and two $4$s, so it will decay into the googlement $1002$. This has one $1$, one $2$, zero $3$s, and zero $4$s, so it will decay into $1100$, which will decay into $2000$, which will decay into $0100$, which will decay into $1000$, which will continuously decay into itself.

You have just observed a googlement $G$. This googlement might have just appeared in the world, or it might be the result of one or more decay steps. What is the total number of possible googlements it could have been when it originally appeared in the world?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each consists of one line with a string $G$, representing a googlement.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of different googlements that the observed googlement could have been when it first appeared in the world.

3
20
1
123

Case #1: 4
Case #2: 1
Case #3: 1

提示

Sample Explanation

In sample case #1, the googlement could have originally been $20$, or it could have decayed from $11$, which could have itself decayed from $12$ or $21$. Neither of the latter two could have been a product of decay. So there are four possibilities in total.

In sample case #2, the googlement must have originally been $1$, which is the only possible googlement of length $1$.

In sample case #3, the googlement must have been $123$; no other googlement could have decayed into it.

Limits

• $1 \leq T \leq 100$.
• Each digit in $G$ is a decimal digit between $0$ and the length of $G$, inclusive.
• $G$ contains at least one non-zero digit.

Small dataset (3 Pts, Test Set 1 - Visible)

• Time limit: 20 5 seconds.
• $1 \leq$ the length of G $\leq 5$.

Large dataset (10 Pts, Test Set 2 - Hidden)

• Time limit: 60 15 seconds.
• $1 \leq$ the length of G $\leq 9$.