전쟁까지 남은 최소 초

2100년, 외계인이 지구에 왔다. 아무도 읽을 수 없는 언어로 쓴 전언을 남기고, 그 옆에 기호를 한 줄 늘어놓았다. 이 기호 줄은 하나의 수를 나타내며, 그 수는 전쟁이 시작되기까지 남은 초다.

기호 하나가 무엇을 뜻하는지는 아무도 모른다. 기호 하나가 숫자 한 자리를 나타낸다는 사실만 확실하고, 어떤 기호가 어떤 숫자인지도, 외계인이 몇 진법을 쓰는지도 모른다. 예를 들어 ab2ac999라고 썼다면 10진법의 31536000, 즉 정확히 1년일 수도 있고, 6진법의 12314555, 즉 398951초로 나흘 반 남짓일 수도 있다.

확실한 것은 세 가지다. 이 수는 양수이고, 외계인도 우리처럼 수를 0으로 시작하지 않으며, 1진법은 쓰지 않는다.

전언이 나타낼 수 있는 가장 작은 초를 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 전언이 한 줄에 하나씩 주어진다. 각 전언은 a부터 z, 0부터 9까지의 문자로만 이루어지고 공백과 문장 부호는 없다. 테스트 케이스는 서로 독립이므로 전언마다 진법이 다를 수 있고, 같은 기호가 다른 숫자를 뜻할 수 있다.

• $1 \le T \le 100$
• 각 전언의 길이는 $1$ 이상 $60$ 이하
• 답은 $10^{18}$을 넘지 않는다

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

Case #X: V

$X$는 1부터 시작하는 테스트 케이스 번호이고, $V$는 전쟁이 시작되기까지 남은 최소 초다.