16030 | 여러 진법에서의 행복

정수 N이 주어지면, N을 각 자릿수의 제곱의 합으로 바꾼다. 행복한 수란 이 과정을 반복해서 적용했을 때 결국 수 1이 되는 수이다. 예를 들어 82에서 시작하면 다음과 같다.

8*8 + 2*2       = 64 + 4    = 68,  repeat:
6*6 + 8*8       = 36 + 64   = 100, repeat:
1*1 + 0*0 + 0*0 = 1 + 0 + 0 = 1 (happy! :)

이 과정의 결과가 1이므로, 82은 행복한 수이다.

어떤 수는 일부 진법에서는 행복한 수이지만 다른 진법에서는 행복한 수가 아닐 수도 있다는 점에 유의하라. 예를 들어, 10진법의 수 82은 3진법으로 나타냈을 때(10001) 행복한 수가 아니다.

당신은 세계 최고의 수 탐정 중 한 명이다. 몇몇 진법들이 한데 모여(그렇다, 이들은 조직되어 있다!) 중요한 임무를 맡기려고 당신을 고용했다. 1보다 크면서 주어진 모든 진법에서 행복한 가장 작은 정수를 찾아내라.

시간 제한: 테스트 세트당 60초. 메모리 제한: 1 GB. 2 가능한 모든 입력 진법 ≤ ≤ 10

1 ≤ T ≤ 42

2 각 테스트 케이스의 진법 개수 ≤ ≤ 3

1 ≤ T ≤ 500

2 각 테스트 케이스의 진법 개수 ≤ ≤ 9

입력의 첫 번째 줄에는 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스는 한 줄로 이루어진다. 각 줄에는 진법을 나타내는 서로 다른 정수의 목록이 공백으로 구분되어 주어진다. 진법 목록은 항상 오름차순이다.

각 테스트 케이스에 대해 다음을 출력한다.

Case #X: K

여기서 X는 1부터 시작하는 테스트 케이스 번호이고, K는 1보다 크면서 주어진 모든 진법에서 행복한 가장 작은 정수의 십진법 표기이다.

Case #1: 3
Case #2: 143
Case #3: 91

문제를 푸는 데 사용한 모든 코드를 제출해야 한다는 점을 기억하라.