모호한 부호문

위성이 어느 날 외계 통신 신호를 가로챘다. 비밀 메시지는 숫자만으로 부호화되어 전송되고 있었고, 숫자는 알파벳을 그대로 치환한 것이었다. 부호화 규칙은 A를 1, B를 2, C를 3으로 옮기는 방식이고, 마지막으로 Z는 26에 대응한다.

위성의 계산 능력은 제한되어 있으므로, 하나의 부호문이 몇 개의 원문에서 나올 수 있는지부터 알아야 한다. 예를 들어 127은 "ABG"와 "LG", 두 원문의 부호문이다. 123은 "ABC", "LC", "AW", 세 원문의 부호문이다.

부호문이 주어질 때 그 부호문으로 부호화되는 원문의 개수를 구하는 프로그램을 작성한다. 그런 원문이 하나도 없으면 0을 출력한다.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다 ($1 \le N \le 100$).

다음 $N$개의 줄에 각각 부호문을 나타내는 문자열이 하나씩 주어진다. 각 문자열은 0부터 9까지의 숫자로만 이루어지고, 길이는 1자 이상 100자 이하이다.

각 테스트 케이스마다 한 줄에 Case #n: k 형식으로 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호이고, $k$는 그 부호문으로 부호화되는 원문의 개수다. $k$는 64비트 정수 범위를 넘을 수 있다.