welcome to code jam 부분 수열 세기

길이가 19인 문자열 welcome to code jam이 주어진 텍스트 안에 부분 수열로 몇 번 나타나는지 센다.

정확히 말하면, 텍스트를 $t$라 하고 $s[0] < s[1] < \cdots < s[18]$을 만족하는 인덱스 수열 $s$를 생각한다. 이때 $t[s[0]]$, $t[s[1]]$, ..., $t[s[18]]$을 순서대로 이어 붙인 문자열이 welcome to code jam과 같아지는 $s$가 몇 개인지 구한다. 문자가 같아도 위치가 다르면 서로 다른 방법으로 센다.

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

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

• $1 \le N \le 100$
• 각 줄의 길이는 1자 이상 500자 이하다.

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