은하 보너스

은하 연합 의회는 지지율이 떨어지자 나이(년 단위)가 둥근 수인 시민에게 보너스를 주기로 했다. 표준 은하 달력 덕분에 모든 행성에서 1년의 길이가 같다.

종족마다 수 체계의 진법이 달라서 '둥근 수'를 정할 수 없다는 반대가 있었다. 의회는 긴 논의 끝에, 나이 $A$를 어떤 진법 $B$에서 $100\ldots100\ldots$ 형태로 쓸 수 있으면 둥근 수로 본다고 정했다. 즉 1이 정확히 두 개 있고 나머지 자리는 모두 0인 수다. 보너스 금액은 $A$가 둥근 수가 되는 가장 작은 진법 $B$이다.

법이 시행되자 의회는 보너스를 빠르게 계산할 방법이 필요해졌다. 시민 수 $N$과 각 시민의 나이 $A_i$가 주어질 때, 각 나이가 둥근 수가 되는 가장 작은 진법을 구하라.

첫 줄에 시민의 수 $N$이 주어진다. 다음 $N$개의 줄에는 시민의 나이 $A_i$가 한 줄에 하나씩 주어진다.

$N$개의 줄을 출력한다. $i$번째 줄에는 $A_i$가 둥근 수가 되는 가장 작은 진법을 출력한다.

$1 \le N \le 100{,}000$

모든 $i$에 대해 $3 \le A_i \le 2^{64} - 1$이다.

$36 = 100100_2$

$26 = 101_5$

$80 = 1010000_2$

$56 = 110_7$

$125 = 11_{124}$

여러 진법에서 둥근 수가 되는 경우도 있다. 예를 들어 36은 진법 3에서도 둥근 수이며, $36 = 1100_3$이다. 하지만 답은 가장 작은 진법이어야 하므로 36의 답은 2이다.