구글먼트

화학자들은 주기율표의 원소를 다루지만, 여기 Code Jam에서는 고급 숫자 분쇄기를 사용해 구글먼트를 연구해 왔다. 구글먼트는 최대 아홉 자리의 문자열로 나타낼 수 있는 물질이다. 길이가 L인 구글먼트에는 0부터 L까지 범위의 십진수 숫자만 포함되어야 하며, 0보다 큰 숫자가 적어도 하나 포함되어야 한다. 선행하는 영은 허용된다. 예를 들어, 103와 001는 길이가 3인 유효한 구글먼트이다. 400(구글먼트의 길이인 3보다 큰 숫자 4을 포함한다)과 000(0보다 큰 숫자를 포함하지 않는다)는 유효하지 않다.

유효한 구글먼트는 언제든 세상에 나타날 수 있지만, 결국 다음과 같은 결정론적 방식으로 다른 구글먼트로 붕괴한다. 길이가 L인 구글먼트에서 1의 개수(0일 수도 있다)를 세어 그 값을 적은 다음, 구글먼트에서 2의 개수(0일 수도 있다)를 세어 앞서 적은 값의 오른쪽에 그 값을 적는다. 이 과정을 계속하여 마지막에는 L의 개수를 세어 적는다. 이 방식으로 생성된 새 문자열은 새로운 구글먼트를 나타내며, 그 길이 역시 L이다. 구글먼트가 자기 자신으로 붕괴하는 것도 가능하다!

예를 들어, 구글먼트 0414가 방금 나타났다고 하자. 여기에는 1이 하나, 2이 영 개, 3이 영 개, 4가 두 개 있으므로 구글먼트 1002로 붕괴한다. 여기에는 1이 하나, 2가 하나, 3이 영 개, 4가 영 개 있으므로 1100로 붕괴한다. 이는 2000으로 붕괴하고, 이는 0100로 붕괴하며, 이는 1000로 붕괴한 뒤 계속해서 자기 자신으로 붕괴한다.

당신은 방금 구글먼트 G를 관찰했다. 이 구글먼트는 방금 세상에 나타난 것일 수도 있고, 한 번 이상의 붕괴 단계를 거친 결과일 수도 있다. 이 구글먼트가 처음 세상에 나타났을 때의 구글먼트로 가능한 것의 총개수는 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. G의 각 숫자는 0부터 G의 길이까지 범위에 포함되는 십진수 숫자이다. G에는 영이 아닌 숫자가 적어도 하나 포함된다.

작은 데이터 세트 (Test Set 1 - 공개)

시간 제한: 20초. 1 ≤ G의 길이 ≤ 5.

큰 데이터 세트 (Test Set 2 - 비공개)

시간 제한: 60초. 1 ≤ G의 길이 ≤ 9.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 구글먼트를 나타내는 문자열 G가 있는 한 줄로 구성된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y은 관찰한 구글먼트가 세상에 처음 나타났을 때의 구글먼트로 가능한 서로 다른 구글먼트의 개수이다.

예제 케이스 #1에서 구글먼트는 원래 20였을 수도 있고, 12 또는 21에서 붕괴했을 수도 있는 11에서 붕괴했을 수도 있다. 뒤의 두 구글먼트 중 어느 것도 붕괴의 결과로 만들어질 수 없다. 따라서 가능한 경우는 모두 네 가지이다.

예제 케이스 #2에서 구글먼트는 원래 반드시 1였으며, 이는 길이가 1인 유일하게 가능한 구글먼트이다.

예제 케이스 #3에서 구글먼트는 반드시 123였으며, 다른 어떤 구글먼트도 이것으로 붕괴할 수 없다.