Lazy Spelling Bee (Small)

In the Lazy Spelling Bee, a contestant is given a target word $W$ to spell. An answer word $A$ is acceptable when both of these hold.

• $A$ has the same length as $W$.
• For every $i$, the $i$-th letter of $A$ equals the $(i-1)$-th, $i$-th, or $(i+1)$-th letter of $W$.

$W$ has no $0$-th letter, so the first letter of $A$ must equal the first or the second letter of $W$. In the same way, the last letter of $A$ must equal the last or the next to last letter of $W$. The target word itself is always an acceptable answer.

For each target word, count the distinct acceptable answer words. The count can be very large, so print it modulo $10^9 + 7$.

The first line contains the number of test cases $T$. Each of the following $T$ lines contains one string made only of lowercase English letters (a through z).

Limits

• $1 \le T \le 100$
• The length of each string is between $1$ and $5$.

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 distinct acceptable answer words modulo $10^9 + 7$.

For the target word ag, the acceptable answers are aa, ag, ga, and gg, so there are four. For the target word aa, the only acceptable answer is aa.