{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDado un entero $n$ y un entero $k$.\u003c/p\u003e\n\u003cp\u003eEn un paso, uno puede realizar alguno de los siguientes movimientos:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e Restar $1$ a $n$.\u003c/li\u003e\n\u003cli\u003e Dividir $n$ entre $k$ en caso sea divisible.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003ePor ejemplo, para $n \u003d 27$ y $k \u003d 3$, puedes realizar los siguientes movimientos:\n$27 \\rightarrow 26 \\rightarrow 25 \\rightarrow 24 \\rightarrow 8 \\rightarrow 7 \\rightarrow 6 \\rightarrow 2 \\rightarrow 1 \\rightarrow 0$.\u003c/p\u003e\n\n\u003cp\u003eTu tarea es calcular el menor número de movimientos para llegar desde $n$ hasta $0$. \u003c/p\u003e"}},{"title":"Entrada","value":{"format":"HTML","content":"\u003cp\u003eLa primera línea contiene un entero $t$ ($1 \\le t \\le 100$) — el número de casos.\u003c/p\n\u003cp\u003eLa única línea de cada caso contiene dos enteros $n$ y $k$ ($1 \\le n \\le 10^{18}$, $2 \\le k \\le 10^{18}$).\u003c/p\u003e"}},{"title":"Salida","value":{"format":"HTML","content":"\u003cp\u003ePara cada caso, imprime el menor número de pasos para alcanzar $0$ desde $n$.\u003c/p\u003e"}},{"title":"Ejemplos","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eEntrada\u003c/th\u003e\n \u003cth\u003eSalida\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n59 3\n1000000000000000000 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n19\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Explicación","value":{"format":"HTML","content":"\u003cp\u003eLos pasos para el primer caso son $59 \\rightarrow 58 \\rightarrow 57 \\rightarrow 19 \\rightarrow 18 \\rightarrow 6 \\rightarrow 2 \\rightarrow 1 \\rightarrow 0$.\u003c/p\u003e\n\u003cp\u003eEn el segundo caso divide $n$ entre $k$ $18$ veces y luego resta $1$ a $n$.\u003c/p\u003e"}}]}