删边

题目描述

对 $T$ 个测试用例分别求解以下问题。

我们有一棵深度为 $D$ 的完美 $K$ 叉树(包含 $1+K+K^2+\dots+K^D$ 个顶点)。

目标是删除若干条边,得到一个恰好包含 $X$ 个顶点的连通分量。

至少需要删除多少条边才能达成目标?

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• 输入中的所有值均为整数。
• $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}$