P16593 [GKS 2016 #E] Beautiful Numbers

We consider a number to be beautiful if it consists only of the digit $1$ repeated one or more times. Not all numbers are beautiful, but we can make any base $10$ positive integer beautiful by writing it in another base. Given an integer $N$, can you find a base $B$ (with $B > 1$) to write it in such that all of its digits become $1$? If there are multiple bases that satisfy this property, choose the one that maximizes the number of $1$ digits.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of one line with an integer $N$.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$) and $y$ is the base described in the problem statement.

In case #$1$, the optimal solution is to write $3$ as $11$ in base $2$. In case #$2$, the optimal solution is to write $13$ as $111$ in base $3$. Note that we could also write $13$ as $11$ in base $12$ or as $1$ in base $13$, but neither of those representations has as many $1$s. ### Limits $1 \le T \le 100$. **Small dataset (Test set 1 - Visible)** $3 \le N \le 1000$. **Large dataset (Test set 2 - Hidden)** $3 \le N \le 10^{18}$.