既然你已经注册了，我们给你发了一封欢迎邮件，欢迎你参加 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]], \dots, input[s[18]]$ 连接起来正好是字符串“welcome to code jam”。

计算结果可能非常大，为了方便起见，我们只需要你求出结果的最后 4 位数字。

输入格式

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

输出格式

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

数据范围

$1 \le N \le 100$

小数据集（10 分）

每行长度不超过 30 个字符。

大数据集（23 分）

每行长度不超过 500 个字符。

样例

样例输入 1

3
elcomew elcome to code jam
wweellccoommee to code qps jam
welcome to codejam

样例输出 1

Case #1: 0001
Case #2: 0256
Case #3: 0000