{"problem":{"name":"Edge Elimination","description":{"content":"Solve the following problem for $T$ test cases. We have a perfect $K$\\-ary tree of depth $D$ (with $1+K+K^2+\\dots+K^D$ vertices).   Your objective is to cut some of the edges to obtain a connected com","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc290_g"},"statements":[{"statement_type":"Markdown","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?\n\n## Constraints\n\n*   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}$\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc290_g","tags":[],"sample_group":[["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","1\n2\n1\n1\n2\n1\n0\n1\n999999999999999998\n1\n0"]],"created_at":"2026-03-03 11:01:14"}}