P13430 [GCJ 2009 Qualification] Welcome to Code Jam

你已经注册了。我们给你发了一封欢迎邮件，欢迎你来到 code jam。但也许你还没有真正感受到 code jam 的欢迎氛围。这就是为什么我们决定将本题命名为“welcome to code jam”。解决了这道题后，我们希望你能感受到真正的欢迎。真正的欢迎，当然，是来自 code jam。 如果你读了上面这段话，你可能会疑惑它为什么会出现在这里。但如果你非常仔细地阅读，你会发现我们已经多次写下了“welcome to code jam”这句话：总共 400263727 次。毕竟，在这段话中，你完全可以先找到一个 'w'，再找到后面的一个 'e'，再找到后面的一个 'l'，如此下去。你的任务是编写一个程序，统计任意给定文本中，子序列“welcome to code jam”出现了多少次。 更准确地说，给定一个文本字符串，请你确定字符串“welcome to code jam”作为**子序列**在该字符串中出现了多少次。换句话说，找到一个严格递增的下标序列 $s$，使得 input[s[0]]、input[s[1]]、……、input[s[18]] 拼接起来恰好是“welcome to code jam”。 由于结果可能非常大，为了方便，只需要输出答案的最后四位数字。

输入的第一行是测试用例数 $N$。接下来的 $N$ 行，每行一个测试用例。每个测试用例是一行文本，仅包含小写字母和空格。每一行都不会以空格开头或结尾。

对于每个测试用例，输出一行 "Case #$x$: $dddd$"，其中 $x$ 是测试编号，$dddd$ 是答案的后四位数字。如果答案不足四位，请在前面补零，使其恰好为四位。

**限制条件** - $1 \leq N \leq 100$ **小数据集（10 分）** - 每行长度不超过 $30$ 个字符。 **大数据集（23 分）** - 每行长度不超过 $500$ 个字符。 翻译由 ChatGPT-4.1 完成。