Code Jam에 오신 것을 환영합니다

등록을 마쳤다. 여러분을 Code Jam에 환영하기 위해 환영 이메일을 보냈다. 하지만 여전히 Code Jam에서 환영받는다는 느낌이 들지 않을 수도 있다. 그래서 문제 이름을 "Code Jam에 오신 것을 환영합니다."로 정하기로 했다. 이 문제를 해결한 뒤에는 여러분이 크게 환영받는다는 느낌을 받기를 바란다. 아주 크게 말이다. 물론 Code Jam에서 말이다.

앞 문단을 읽었다면 아마 왜 그런 내용이 있는지 궁금할 것이다. 하지만 아주 주의 깊게 읽어 보면 "Code Jam에 오신 것을 환영합니다"라는 말을 여러 번, 즉 총 400263727번 썼다는 것을 알아챌 수도 있다. 결국 문단을 훑어 'w'를 찾고, 문단의 더 뒤에서 'e'를 찾고, 그 뒤에서 'l'을 찾는 식으로 계속하는 것은 쉽다. 여러분의 과제는 임의의 텍스트를 받아 그 텍스트에 "Code Jam에 오신 것을 환영합니다"라는 구절이 몇 번 포함되는지 출력할 수 있는 프로그램을 작성하는 것이다.

더 정확히 말하면, 텍스트 문자열이 주어질 때 문자열 "Code Jam에 오신 것을 환영합니다"가 그 문자열의 부분 수열로 몇 번 나타나는지 구해야 한다. 다시 말해, 입력 문자열에서 증가하는 인덱스들로 이루어진 수열 s를 찾아 input[s[0]], input[s[1]], ..., input[s[18]]를 이어 붙인 문자열이 "Code Jam에 오신 것을 환영합니다"가 되도록 한다.

계산 결과가 매우 클 수 있으므로, 편의를 위해 마지막 4자리만 구한다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB.

1 ≤ N ≤ 100

작은 데이터 세트

각 줄은 30자를 넘지 않는다.

큰 데이터 세트

각 줄은 500자를 넘지 않는다.

입력의 첫 줄에는 테스트 케이스의 수 N이 주어진다. 이어지는 N개의 입력 줄에는 각각 하나의 테스트 케이스가 들어 있다. 각 테스트 케이스는 소문자와 공백만 포함하는 한 줄의 텍스트이다. 어떤 줄도 공백으로 시작하지 않으며, 어떤 줄도 공백으로 끝나지 않는다.

각 테스트 케이스에 대해 "Case #x: dddd"를 출력한다. 여기서 x는 테스트 케이스 번호이고, 그 뒤의 네 자리는 답의 마지막 네 자리이다. 답이 4자리보다 짧다면, 앞에 영을 추가하여 정확히 4자리로 만든다.