Little Mono is a smart child, he can do complex arithmetical operations quickly. But he only knows one digit $D(1 \leq D \leq 9)$. He would like to use the only digit he knows to make expressions to represent integer numbers.
A valid expression can be generated like this:
1. Any number consists of only digit $D$ are valid expressions. E.g. if $D = 1$, then 1, 11, 111, ... are all valid expressions.
2. If $A$ and $B$ are valid expressions, then $(A) + (B)$ is a valid expression.
3. If $A$ and $B$ are valid expressions, then $(A) - (B)$ is a valid expression.
4. If $A$ and $B$ are valid expressions, then $(A) * (B)$ is a valid expression.
5. If $A$ and $B$ are valid expressions, then $(A)/(B)$ is a valid expression. (/ here produces exact value, not integer division)
6. If $A$ and $B$ are valid expressions, then $(A)^{(B)}$ is a valid expression.
7. If $A$ is valid expression, then $\sqrt{A}$ is a valid expression.
8. If $A$ is valid expression, then $(A)!$ is a valid expression.(! here means factorial, and expression $A$ must produce a non-negative integer)
Now Little Mono would like to know the minimal number of $D$s he needs to use in order to represent integer $N$.
Input
The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
Each test case contains one line consists of 2 integers $D$, $N$, indicating the digit Little Mono knows and the integer Little Mono would like to represent.
$1 \leq T \leq 100$
$1 \leq D \leq 9$
$1 \leq N \leq 200$
Output
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 minimal number of $D$s Little Mono has to use.