아름다운 수 (Small)

숫자 1이 한 번 이상 반복된 형태로만 적히는 수를 아름다운 수라고 하자. 10진법에서 모든 수가 아름답지는 않지만, 양의 정수를 다른 진법으로 바꿔 적으면 아름답게 만들 수 있다.

정수 $N$이 주어진다. $N$을 $B$진법($B > 1$)으로 적었을 때 모든 자리가 1이 되는 $B$를 찾아라. 조건을 만족하는 $B$가 여러 개면 1의 개수가 가장 많아지는 $B$를 고른다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 각각 정수 $N$이 하나씩 주어진다.

제한

• $1 \le T \le 100$
• $3 \le N \le 1000$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 문제에서 설명한 $B$이다.

$N = 3$이면 2진법으로 적은 11이 가장 좋은 답이므로 $B$는 2이다.

$N = 13$이면 3진법으로 적은 111이 가장 좋은 답이므로 $B$는 3이다. 13은 12진법에서 11로도 적히지만, 1의 개수가 더 적다.