{"problem":{"name":"[ICPC 2018 Qingdao R] Function and Function","description":{"content":"If we define $f(0) = 1, f(1) = 0, f(4) = 1, f(8) = 2, f(16) = 1, \\dots$, do you know what function $f$ means? Actually, $f(x)$ calculates the total number of enclosed areas produced by each digit in ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9897"},"statements":[{"statement_type":"Markdown","content":"If we define $f(0) = 1, f(1) = 0, f(4) = 1, f(8) = 2, f(16) = 1, \\dots$, do you know what function $f$ means?\n\nActually, $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:\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/sdv14tzu.png)\n\nFor example, $f(1234) = 0 + 0 + 0 + 1 = 1$, and $f(5678) = 0 + 1 + 0 + 2 = 3$.\n\nWe now define a recursive function $g$ by the following equations: \n\n$$\\begin{cases} g^0(x) = x \\\\ g^k(x) = f(g^{k-1}(x)) & \\text{if } k \\ge 1 \\end{cases}$$\n\nFor example, $g^2(1234) = f(f(1234)) = f(1) = 0$, and $g^2(5678) = f(f(5678)) = f(3) = 0$.\n\nGiven two integers $x$ and $k$, please calculate the value of $g^k(x)$.\n\n## Input\n\nThere 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:\n\nThe 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 `0'.\n\n## Output\n\nFor each test case output one line containing one integer, indicating the value of $g^k(x)$.\n\n[samples]\n\n## Note\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/fjjr5xin.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9897","tags":["2018","O2优化","ICPC","青岛"],"sample_group":[["6\n123456789 1\n888888888 1\n888888888 2\n888888888 999999999\n98640 12345\n1000000000 0","5\n18\n2\n0\n0\n1000000000"]],"created_at":"2026-03-03 11:09:25"}}