Problem Description

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.

Input Format

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$.

Output Format

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.

2
3
13

2
3

Hint

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}$.