{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIf we define $f(0) \u003d 1, f(1) \u003d 0, f(4) \u003d 1, f(8) \u003d 2, f(16) \u003d 1, \\dots$, do you know what function $f$ means?\u003c/p\u003e\n\n\u003cp\u003eActually, $f(x)$ calculates the total number of enclosed areas produced by each digit in $x$. The following table shows the number of enclosed areas produced by each digit:\u003c/p\u003e\n\n\u003ctable id\u003d\"problem-table\" style\u003d\"border-collapse: collapse; text-align: center;\" align\u003d\"center\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\u003cth\u003eDigit\u003c/th\u003e\u003cth\u003eEnclosed Area\u003c/th\u003e\u003cth\u003eDigit\u003c/th\u003e\u003cth\u003eEnclosed Area\u003c/th\u003e\u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\u003ctd\u003e0\u003c/td\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003e5\u003c/td\u003e\u003ctd\u003e0\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003e0\u003c/td\u003e\u003ctd\u003e6\u003c/td\u003e\u003ctd\u003e1\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e2\u003c/td\u003e\u003ctd\u003e0\u003c/td\u003e\u003ctd\u003e7\u003c/td\u003e\u003ctd\u003e0\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e3\u003c/td\u003e\u003ctd\u003e0\u003c/td\u003e\u003ctd\u003e8\u003c/td\u003e\u003ctd\u003e2\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e4\u003c/td\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003e9\u003c/td\u003e\u003ctd\u003e1\u003c/td\u003e\u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003eFor example, $f(1234) \u003d 0 + 0 + 0 + 1 \u003d 1$, and $f(5678) \u003d 0 + 1 + 0 + 2 \u003d 3$.\u003c/p\u003e\n\n\u003cp\u003eWe now define a recursive function $g$ by the following equations: $\\begin{cases} g^0(x) \u003d x \\\\ g^k(x) \u003d f(g^{k-1}(x)) \u0026amp; \\text{if } k \\ge 1 \\end{cases}$\u003c/p\u003e\n\n\u003cp\u003eFor example, $g^2(1234) \u003d f(f(1234)) \u003d f(1) \u003d 0$, and $g^2(5678) \u003d f(f(5678)) \u003d f(3) \u003d 0$.\u003c/p\u003e\n\n\u003cp\u003eGiven two integers $x$ and $k$, please calculate the value of $g^k(x)$.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$ (about $10^5$), indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first and only line contains two integers $x$ and $k$ ($0 \\le x, k \\le 10^9$). Positive integers are given without leading zeros, and zero is given with exactly one \u00270\u0027.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing one integer, indicating the value of $g^k(x)$.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e6\n123456789 1\n888888888 1\n888888888 2\n888888888 999999999\n98640 12345\n1000000000 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n18\n2\n0\n0\n1000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/c5d3acad21ebb75c69f51f9290b39888?v\u003d1715371145\" width\u003d\"150px\"\u003e\n\n\u003cstyle type\u003d\"text/css\"\u003e\n#problem-table \u003e thead \u003e tr \u003e th, #problem-table \u003e tbody \u003e tr \u003e td\n{\n padding: 3px 5px;\n border: 1px solid black;\n}\n\u003c/style\u003e\n"}}]}