여러 진법에서 행복한 수 (작은 입력)

정수 $N$을 각 자리 숫자의 제곱의 합으로 바꾼다. 이 과정을 계속 반복해서 결국 1이 되는 수를 행복한 수라고 한다. 82에서 시작하면 다음과 같다.

8*8 + 2*2       = 64 + 4    = 68,  다시:
6*6 + 8*8       = 36 + 64   = 100, 다시:
1*1 + 0*0 + 0*0 = 1 + 0 + 0 = 1 (행복하다!)

과정이 1로 끝났으므로 82는 행복한 수다.

$b$진법에서 행복하다는 말은, 수를 $b$진법으로 쓴 뒤 각 자리 숫자의 제곱을 더하는 과정을 반복해서 1에 도달한다는 뜻이다. 같은 수라도 어떤 진법에서는 행복하고 다른 진법에서는 행복하지 않을 수 있다. 10진법의 82를 3진법으로 쓰면 10001인데, 3진법에서 82는 행복한 수가 아니다.

진법들이 모여서(그렇다, 조직까지 만들었다) 당신에게 일을 맡겼다. 주어진 진법 전부에서 행복한, 1보다 큰 가장 작은 정수를 찾아라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 다음 $T$개의 줄에 테스트 케이스가 한 줄씩 주어진다. 각 줄에는 서로 다른 진법이 공백으로 구분되어 증가하는 순서로 나열된다.

제한

• $1 \le T \le 42$
• 각 줄에 나열되는 진법은 2개 또는 3개
• 입력에 나오는 모든 진법 $b$는 $2 \le b \le 10$

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

Case #X: K

$X$는 1부터 시작하는 테스트 케이스 번호이고, $K$는 주어진 진법 전부에서 행복한, 1보다 큰 가장 작은 정수를 10진법으로 나타낸 값이다.