구글먼트 (Large)

길이가 $L$인 구글먼트는 0 이상 $L$ 이하의 숫자로만 이루어진 길이 $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 \le T \le 100$
• $G$의 길이는 1 이상 9 이하다.
• $G$의 각 숫자는 0 이상 $G$의 길이 이하다.
• $G$에는 0이 아닌 숫자가 적어도 하나 있다.

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

예제의 첫 번째 구글먼트 20은 처음부터 20이었을 수도 있고, 11이 붕괴한 결과일 수도 있다. 11은 다시 12나 21이 붕괴해서 나올 수 있는데, 12와 21로 붕괴하는 구글먼트는 없다. 그래서 가능한 구글먼트는 모두 네 개다.

두 번째 구글먼트 1은 길이가 1인 유일한 구글먼트이므로 답은 1이다.

세 번째 구글먼트 123으로 붕괴하는 구글먼트는 없으므로 123 자신만 가능하다.