当前没有测试数据。

G - 边的删除

分数：$600$ 分

题目描述

解决以下问题的 $T$ 次测试案例。

我们有一棵深度为 $D$ 的完美 $K$-叉树（包含 $1+K+K^2+\dots+K^D$ 个结点）。
你的目标是切断一些边，以获得具有恰好 $X$ 个结点的连通分量。
至少需要切断多少条边才能实现这个目标？

约束

• 输入中的所有值均为整数。
• $1 \le T \le 100$
• $1 \le D$
• $2 \le K$
• $\displaystyle 1 \le X \le \sum_{i=0}^{D} K^i \le 10^{18}$

---

输入

从标准输入中以以下格式给出输入：

$T$

$case_1$

$\vdots$

$case_T$

这里，$case_i$ 表示第 $i$ 个测试案例。
每个测试案例以以下格式给出：

``` $D$ $K$ $X$ ```

输出

输出 $T$ 行。
第 $i$ 行应该包含第 $i$ 个测试案例的答案作为一个整数。

---

11
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
1 999999999999999999 1
1 999999999999999999 2
1 999999999999999999 999999999999999999
1 999999999999999999 1000000000000000000

1
2
1
1
2
1
0
1
999999999999999998
1
0