{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eLittle 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.\u003cbr\u003eA valid expression can be generated like this:\u003cbr\u003e 1. Any number consists of only digit $D$ are valid expressions. E.g. if $D \u003d 1$, then 1, 11, 111, ... are all valid expressions.\u003cbr\u003e 2. If $A$ and $B$ are valid expressions, then $(A) + (B)$ is a valid expression.\u003cbr\u003e 3. If $A$ and $B$ are valid expressions, then $(A) - (B)$ is a valid expression.\u003cbr\u003e 4. If $A$ and $B$ are valid expressions, then $(A) * (B)$ is a valid expression.\u003cbr\u003e 5. If $A$ and $B$ are valid expressions, then $(A)/(B)$ is a valid expression. (/ here produces exact value, not integer division)\u003cbr\u003e 6. If $A$ and $B$ are valid expressions, then $(A)^{(B)}$ is a valid expression.\u003cbr\u003e 7. If $A$ is valid expression, then $\\sqrt{A}$ is a valid expression.\u003cbr\u003e 8. If $A$ is valid expression, then $(A)!$ is a valid expression.(! here means factorial, and expression $A$ must produce a non-negative integer)\u003cbr\u003eNow Little Mono would like to know the minimal number of $D$s he needs to use in order to represent integer $N$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input gives the number of test cases, $T$. $T$ test cases follow.\u003cbr\u003eEach 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.\u003cbr\u003e$1 \\leq T \\leq 100$\u003cbr\u003e$1 \\leq D \\leq 9$\u003cbr\u003e$1 \\leq N \\leq 200$"}},{"title":"Output","value":{"format":"HTML","content":"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."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1 10\r\n4 64\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 3\r\nCase #2: 2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/95308240957099c78b9e0023b23a9981?v\u003d1715139952\"\u003e\u003c/center\u003e \u003cbr\u003e"}}]}