Beautiful Numbers (Large)

Time limit5sMemory limit512 MB

Summary

For each N up to 1e18, find the base B that writes N with all digits 1, preferring the base that gives the most 1 digits.

Level: Hard8 of 10
Topics: Number theory, Math, Binary search, Brute force
Solved: No attempts yet

Problem

Call a number beautiful if every one of its digits is 1. A number that is not beautiful in base 10 can still 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 satisfy this, choose the one that maximizes the number of 1 digits.

Input

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

Limits

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

Output

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

Hint

For $N = 3$ , the answer is 2, because 3 is written as 11 in base 2.

For $N = 13$ , the answer is 3, because 13 is written as 111 in base 3. You could also write 13 as 11 in base 12, but that representation has fewer 1 digits.

Examples2

Example 1
Input
```
2
3
13
```
Expected output
```
Case #1: 2
Case #2: 3
```

Example 2

Input

Expected output

Case #1: 3
Case #2: 4
Case #3: 5
Case #4: 2
Case #5: 7