못생긴 수

옛날 어느 기묘한 상황에서, 사람들은 어떤 수가 한 자리 소수 중 하나(2, 3, 5 또는 7)로 나누어떨어지면 그 수를 못생겼다고 불렀다. 따라서 14은 못생겼지만, 13은 괜찮다. 39은 못생겼지만, 121은 그렇지 않다. 0은 못생긴 수라는 점에 유의한다. 또한 음수도 못생길 수 있다는 점에 유의한다. -14과 -39이 그러한 수의 예이다.

어느 날 한가한 시간에 다음과 같은 숫자 문자열을 바라보고 있다.

123456

숫자 사이에 더하기 또는 빼기 기호를 삽입할 수 있을 때 얼마나 많은 가능성이 있는지 흥미롭게 느낀다. 예를 들어 다음을 만들 수 있다.

1 + 234 - 5 + 6 = 236

이는 못생겼다. 또는 다음을 만들 수 있다.

123 + 4 - 56 = 71

이는 못생기지 않았다.

숫자를 가지고 만들 수 있는 서로 다른 방법의 수를 세는 것은 쉽다. 인접한 두 숫자 사이마다 더하기 기호를 넣거나, 빼기 기호를 넣거나, 아무것도 넣지 않는 것 중 하나를 선택할 수 있다. 따라서 D개의 숫자로 시작하면 만들 수 있는 식은 3^{D-1}개이다.

수에 선행하는 영이 있어도 괜찮다는 점에 유의한다. 문자열이 "01023"이면, "01023", "0+1-02+3", "01-023"은 올바른 식이다.

해야 할 일은 간단하다. 3^{D-1}개의 식 중 계산 결과가 못생긴 수인 식이 몇 개인지 센다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 0 ≤ N ≤ 100. 각 테스트 케이스의 문자열은 비어 있지 않으며, '0'부터 '9'까지의 문자만 포함한다.

작은 데이터 세트 (테스트 세트 1 - 공개)

각 문자열의 길이는 최대 13자이다.

큰 데이터 세트 (테스트 세트 2 - 비공개)

각 문자열의 길이는 최대 40자이다.

입력 파일의 첫째 줄에는 케이스의 수 N이 주어진다. 각 테스트 케이스는 비어 있지 않은 십진 숫자 문자열 하나가 담긴 한 줄로 주어진다.

각 테스트 케이스마다 다음 형식의 한 줄을 출력해야 한다.

Case #X: Y

여기서 X는 1부터 시작하는 케이스 번호이고, Y는 계산 결과가 못생긴 수인 식의 수이다.