너희의 모든 진법

A.D. 2100에 외계인들이 지구에 왔다. 그들은 알 수 없는 언어로 메시지를 쓰고, 그 옆에 일련의 기호를 적었다. 우리는 그 기호들이 하나의 수, 즉 전쟁이 시작되기까지 남은 시간(초)을 나타낸다는 결론에 도달했다!

안타깝게도 각 기호가 무엇을 뜻하는지 전혀 알 수 없다. 각 기호가 하나의 숫자를 나타낸다고 판단했지만, 각 숫자가 무엇을 뜻하는지, 외계인들이 어떤 진법을 사용하는지는 확실하지 않다. 예를 들어 그들이 "ab2ac999"라고 썼다면, 이는 10진법의 "31536000" — 정확히 일 년 — 을 뜻했을 수도 있고, 6진법의 "12314555" — 398951초, 즉 약 나흘 반 — 을 뜻했을 수도 있다. 우리가 확신하는 것은 세 가지이다. 그 수는 양수이고, 외계인들도 우리처럼 수를 영으로 시작하지 않으며, 단항법(1진법)을 사용하지 않는다.

전쟁이 시작되기까지 남을 수 있는 최소 시간을 초 단위로 구한다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100 답은 절대로 $10^{18}$을 초과하지 않는다.

소형 데이터 세트

1 ≤ 각 줄의 길이 < 10

대형 데이터 세트

1 ≤ 각 줄의 길이 < 61

입력의 첫 줄에는 정수 T 하나가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄에 문자열 하나로 주어진다. 이 줄에는 'a'부터 'z'까지와 '0'부터 '9'까지의 범위에 속하는 문자만 포함되며(공백과 문장 부호는 포함되지 않는다), 외계인들이 남긴 메시지를 나타낸다. 테스트 케이스들은 서로 독립적이며, 서로 다른 진법을 사용할 수 있고 기호의 의미도 서로 다를 수 있다.

각 테스트 케이스에 대해 다음 형식으로 한 줄을 출력한다.

Case #X: V

여기서 X는 1부터 시작하는 케이스 번호이고, V는 전쟁이 시작되기까지 남을 수 있는 최소 시간(초)이다.