Beautiful Numbers (Small)

Call a number beautiful if it is written with the digit 1 repeated one or more times. Not every number is beautiful in base 10, but any positive integer can be made beautiful by writing it in another base.

You are given an integer $N$. Find a base $B$ (with $B > 1$) such that every digit of $N$ written in base $B$ is 1. If several bases work, choose the one that gives the most 1 digits.

The first line contains the number of test cases $T$. Each of the following $T$ lines contains one integer $N$.

Limits

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

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the base described above.

For $N = 3$ the best answer is 11 in base 2, so $B$ is 2.

For $N = 13$ the best answer is 111 in base 3, so $B$ is 3. The number 13 is also 11 in base 12, but that form has fewer 1 digits.