16407 | 아름다운 수

어떤 수가 숫자 1만 하나 이상 반복하여 이루어진 경우, 그 수를 아름답다고 한다. 모든 수가 아름다운 것은 아니지만, 밑이 10인 임의의 양의 정수도 다른 진법으로 표기하면 아름답게 만들 수 있다.

정수 N이 주어질 때, 모든 자릿수가 1이 되도록 표기할 수 있는 진법의 밑 B를 찾을 수 있는가(단, B > 1)? 이 성질을 만족하는 밑이 여러 개라면, 1인 자릿수의 개수를 최대화하는 것을 선택한다.

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 30초. 메모리 제한: 1GB.

3 ≤ N ≤ 1000.

3 ≤ N ≤ $10^{18}$ .

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N이 있는 한 줄로 구성된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 문제 설명에서 기술한 밑이다.

2
3
13

Case #1: 2
Case #2: 3

케이스 #1에서 최적해는 3을 밑이 2인 진법의 11으로 표기하는 것이다.

케이스 #2에서 최적해는 13을 밑이 3인 진법의 111으로 표기하는 것이다. 13을 밑이 12인 진법의 11으로 표기하거나 밑이 13인 진법의 1으로 표기할 수도 있지만, 두 표기 모두 1의 개수가 그만큼 많지 않다는 점에 유의한다.