Welcome to Code Jam (Small)

Skim a long paragraph and you can build the phrase "welcome to code jam" out of it: find a 'w', then find an 'e' later on, then an 'l' after that, and so on. The same paragraph gives many different ways to do it, depending on which letters you pick.

Given one line of text, count how many ways "welcome to code jam" appears in it as a subsequence. Formally, let $S$ be the input string and let $T$ = "welcome to code jam". Count the index sequences $s$ with $s[0] < s[1] < \cdots < s[18]$ such that concatenating $S[s[0]], S[s[1]], \ldots, S[s[18]]$ gives $T$. The length of $T$ is 19 including its spaces, and each space of $T$ must also be matched by a space of the input.

The count can be huge, so report 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, a single line of text made of lower-case English letters and spaces. No line starts with a space and no line ends with a space.

Limits

• $1 \le N \le 100$
• Each line is at most 30 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 it is exactly four digits long.