Welcome to Code Jam (작은 입력)

긴 문단 하나를 훑어보면 먼저 'w'를 찾고, 그 뒤에서 'e'를 찾고, 다시 그 뒤에서 'l'을 찾는 식으로 "welcome to code jam"이라는 문구를 얼마든지 만들어 낼 수 있다. 같은 문단이라도 어떤 글자를 고르느냐에 따라 서로 다른 방법이 나온다.

텍스트 한 줄이 주어질 때, 그 안에서 "welcome to code jam"을 부분 수열로 만드는 방법이 몇 가지인지 센다. 정확히 말하면 입력 문자열을 $S$, 목표 문자열을 $T$ = "welcome to code jam"이라 할 때, $s[0] < s[1] < \cdots < s[18]$을 만족하면서 $S[s[0]], S[s[1]], \ldots, S[s[18]]$을 이어 붙인 결과가 $T$와 같아지는 인덱스 수열 $s$의 개수를 구한다. $T$의 길이는 공백을 포함해 19이고, 공백도 반드시 입력의 공백에서 골라야 한다.

답이 매우 커질 수 있으므로 마지막 네 자리만 구한다.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다. 이어지는 $N$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄은 영어 소문자와 공백으로만 이루어지고, 공백으로 시작하거나 끝나지 않는다.

제한

• $1 \le N \le 100$
• 각 줄의 길이는 30자를 넘지 않는다.

각 테스트 케이스마다 Case #x: dddd 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, dddd는 답의 마지막 네 자리이다. 답이 네 자리보다 짧으면 앞을 0으로 채워 정확히 네 자리로 만든다.