Same DigitTime Limit: 40000/20000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 0 Accepted Submission(s): 0
Problem Description 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.
Sample Input
Sample Output
Source 2017中国大学生程序设计竞赛-总决赛-重现赛测试
Hint Statistic | Submit | Clarifications | Back
|