{"raw_statement":[{"iden":"problem statement","content":"Solve the following problem for $T$ test cases.\nWe have a perfect $K$\\-ary tree of depth $D$ (with $1+K+K^2+\\dots+K^D$ vertices).  \nYour objective is to cut some of the edges to obtain a connected component with exactly $X$ vertices.  \nAt least how many edges must be cut to achieve the objective?"},{"iden":"constraints","content":"*   All values in the input are integers.\n*   $1 \\le T \\le 100$\n*   $1 \\le D$\n*   $2 \\le K$\n*   $\\displaystyle 1 \\le X \\le \\sum_{i=0}^{D} K^i \\le 10^{18}$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$\\vdots$\n$case_T$\n\nHere, $case_i$ denotes the $i$\\-th test case.  \nEach test case is given in the following format:\n\n$D$ $K$ $X$"},{"iden":"sample input 1","content":"11\n2 2 1\n2 2 2\n2 2 3\n2 2 4\n2 2 5\n2 2 6\n2 2 7\n1 999999999999999999 1\n1 999999999999999999 2\n1 999999999999999999 999999999999999999\n1 999999999999999999 1000000000000000000"},{"iden":"sample output 1","content":"1\n2\n1\n1\n2\n1\n0\n1\n999999999999999998\n1\n0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}