구글먼트 (작은 입력)

화학자가 주기율표의 원소를 다룬다면, 이 문제에서 다루는 물질은 구글먼트다. 구글먼트는 최대 아홉 자리의 숫자 문자열로 나타낸다. 길이가 $L$인 구글먼트는 0 이상 $L$ 이하의 숫자만 쓰고, 0보다 큰 숫자를 적어도 하나 포함한다. 맨 앞에 0이 와도 된다. 예를 들어 103과 001은 길이가 3인 올바른 구글먼트다. 400은 길이 3보다 큰 숫자 4를 포함하므로 올바르지 않고, 000은 0보다 큰 숫자가 하나도 없으므로 올바르지 않다.

올바른 구글먼트는 언제든 세상에 나타날 수 있고, 시간이 지나면 정해진 방식으로 다른 구글먼트로 붕괴한다. 길이가 $L$인 구글먼트에서 1의 개수를 세어 적고, 그 오른쪽에 2의 개수를 세어 적고, 같은 방식으로 $L$의 개수까지 이어서 적는다. 이렇게 만든 문자열이 새 구글먼트이며, 길이는 그대로 $L$이다. 자기 자신으로 붕괴하는 구글먼트도 있다.

예를 들어 0414가 나타났다고 하자. 1이 한 개, 2가 없고, 3도 없고, 4가 두 개이므로 1002로 붕괴한다. 1002는 1이 한 개, 2가 한 개, 3과 4가 없으므로 1100으로 붕괴하고, 1100은 2000으로, 2000은 0100으로, 0100은 1000으로 붕괴한다. 1000은 계속 자기 자신으로 붕괴한다.

구글먼트 $G$를 관찰했다. $G$는 방금 나타난 것일 수도 있고, 한 번 이상 붕괴한 결과일 수도 있다. $G$가 처음 세상에 나타났을 때의 구글먼트로 가능한 것은 모두 몇 가지인지 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어지는 $T$개의 줄에 구글먼트를 나타내는 문자열 $G$가 한 줄에 하나씩 주어진다.

제한

• 1 ≤ $T$ ≤ 100
• $G$의 각 숫자는 0 이상 $G$의 길이 이하다.
• $G$는 0이 아닌 숫자를 적어도 하나 포함한다.
• $G$의 길이는 1 이상 5 이하다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 관찰한 구글먼트가 처음 나타났을 때의 모습으로 가능한 서로 다른 구글먼트의 개수다.

20을 관찰했다면 처음 나타난 구글먼트는 20 자신일 수도 있고, 20으로 붕괴하는 11일 수도 있다. 11은 12나 21이 붕괴한 결과이기도 하고, 12와 21로 붕괴하는 구글먼트는 없다. 그래서 가능한 경우는 모두 네 가지다.

1을 관찰했다면 길이가 1인 구글먼트는 1뿐이므로 답은 1이다.

123을 관찰했다면 123으로 붕괴하는 다른 구글먼트가 없으므로 답은 1이다.