Counting welcome to code jam subsequences

Count how many times the 19 character string welcome to code jam appears as a subsequence of a given text.

To be precise, let $t$ be the text and consider an index sequence $s$ with $s[0] < s[1] < \cdots < s[18]$. Count the sequences $s$ for which concatenating $t[s[0]]$, $t[s[1]]$, ..., $t[s[18]]$ in that order gives exactly welcome to code jam. Two sequences that pick the same letters from different positions count separately.

The answer can be huge, so print only its last four digits.

The first line contains the number of test cases $N$. Each of the next $N$ lines contains one test case as a single line of text. Every line consists of lowercase English letters and spaces only, and never starts or ends with a space.

• $1 \le N \le 100$
• Each line is between 1 and 500 characters long.

For each test case, print one line in the form Case #x: dddd, where $x$ is the test case number starting from 1 and $dddd$ is the last four digits of the answer. If the answer has fewer than four digits, pad it with leading zeros so that exactly four digits are printed.