여러 진법에서 행복한 수

정수 $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는 행복한 수다.

같은 수라도 어떤 진법에서는 행복하고 다른 진법에서는 행복하지 않다. 10진법의 82를 3진법으로 쓰면 10001이고, 이 진법에서는 1에 도달하지 못한다.

$b$진법에서의 행복한 수는 이렇게 정한다. 수를 $b$진법으로 적고 각 자리 숫자의 제곱을 모두 더해 새로운 수를 얻는다. 이 과정을 반복해서 1이 나오면 그 수는 $b$진법에서 행복하다.

진법 목록이 주어질 때, 1보다 크면서 주어진 모든 진법에서 행복한 가장 작은 정수를 구하라.

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

제한

• 입력에 등장하는 모든 진법 $b$는 $2 \le b \le 10$
• $1 \le T \le 500$
• 각 테스트 케이스의 진법 개수는 2 이상 9 이하

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

Case #X: K

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