{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"为了实现和 Yawara Kai 的约定,Hitori Bocchi 想要和班上的人成为朋友。\n\nHitori Bocchi 的班上有 n 个人是不认识的。每天,Hitori Bocchi 可以和一个人交朋友;但如果当前剩余的人数恰好是 k 的倍数,Hitori Bocchi 可以这些人中的 (k - 1) / k 交朋友。\n\n例如,如果 n \u003d 27, k \u003d 3,剩余人数的变化可以是 27, 26, 25, 24, 8, 7, 6, 2, 1, 0。\n\n为了实现和 Yawara Kai 的约定,Hitori Bocchi 想要尽快和班上的人成为朋友。现在,Sunao Nako 想要知道,Hitori Bocchi 和班上所有人成为朋友所需的最少天数。\n\nSunao Nako 当然会这个问题,但 Sunao Nako 想考考你,所以 Sunao Nako 希望你能解决这个问题。\n\n为了应对不同的情况,你需要回答 Sunao Nako 的 q 次询问。"}},{"title":"Input","value":{"format":"MD","content":"第一行包含一个整数 q (1 \u003c\u003d q \u003c\u003d 100),代表共有 q 次询问。\n\n接下来的 q 行每行包含两个整数 n 和 k (1 \u003c\u003d n \u003c\u003d 10\u003csup\u003e18\u003c/sup\u003e, 2 \u003c\u003d k \u003c\u003d 10\u003csup\u003e18\u003c/sup\u003e)。"}},{"title":"Output","value":{"format":"MD","content":"对于每次询问,输出Hitori Bocchi 和班上所有人成为朋友所需的最少天数。"}},{"title":"Example","value":{"format":"MD","content":"**Input**\n2\n59 3\n1000000000000000000 10\n\n**Output**\n8\n19"}},{"title":"Note","value":{"format":"MD","content":"第一个样例中,剩余人数的变化为 59, 58, 57, 19, 18, 6, 2, 1, 0。\n\n第二个样例中,Hitori Bocchi 可以连续使用第二种操作 18 次,再使用第一种操作。"}}]}