어글리 수가 되는 식 세기

한 자리 소수 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$이 주어진다. 이어지는 $N$개의 줄에는 숫자로만 이루어진 문자열이 한 줄에 하나씩 주어진다.

제한

• $0 \le N \le 100$
• 각 문자열은 비어 있지 않고, 문자 0부터 9까지만 포함한다.
• 각 문자열의 길이는 13 이하다.

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

Case #X: Y

$X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 값이 어글리 수인 식의 개수다.