못생긴 수 (라지)

어떤 수가 한 자리 소수 2, 3, 5, 7 중 하나로 나누어지면 그 수를 못생긴 수라고 부른다. 그래서 14는 못생긴 수지만 13은 아니다. 39는 못생긴 수지만 121은 아니다. 0도 못생긴 수다. 음수도 못생긴 수가 될 수 있다. -14와 -39가 그런 예다.

십진수 숫자로만 이루어진 문자열 하나가 주어진다. 예를 들면 다음과 같다.

123456

인접한 두 숫자 사이마다 더하기 기호, 빼기 기호, 또는 아무것도 넣어서 식을 만들 수 있다. 예를 들어

1 + 234 - 5 + 6 = 236

처럼 만들면 결과 236은 못생긴 수다. 반면

123 + 4 - 56 = 71

의 결과 71은 못생긴 수가 아니다.

만들 수 있는 식의 개수는 세기 쉽다. 인접한 두 숫자 사이마다 더하기, 빼기, 아무것도 넣지 않기 중 하나를 고르므로, 숫자가 $D$개면 식은 $3^{D-1}$개다.

각 수의 앞에 0이 붙어도 된다. 문자열이 "01023"이면 "01023", "0+1-02+3", "01-023"은 모두 올바른 식이다.

$3^{D-1}$개의 식 중에서 값이 못생긴 수가 되는 식이 몇 개인지 세라.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다. 이어지는 각 줄에는 십진수 숫자로만 이루어진, 비어 있지 않은 문자열이 하나씩 주어진다.

제한

• $0 \le N \le 100$
• 각 문자열은 비어 있지 않고 '0'부터 '9'까지의 문자로만 이루어진다.
• 각 문자열의 길이는 40 이하다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.

Case #X: Y

$X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 값이 못생긴 수가 되는 식의 개수다.