아름다운 수 (큰 입력)

모든 자리가 숫자 1로만 이루어진 수를 아름다운 수라고 하자. 10진법으로 적었을 때 아름답지 않은 수라도, 다른 진법으로 적으면 아름다운 수로 만들 수 있다.

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

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

제한

• $1 \le T \le 100$
• $3 \le N \le 10^{18}$

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

$N = 3$이면 2진법으로 적었을 때 11이 되므로 답은 2다.

$N = 13$이면 3진법으로 적었을 때 111이 되므로 답은 3이다. 13을 12진법으로 적으면 11이 되지만, 1의 개수가 더 적다.