题目描述

解决以下问题的$T$个测试用例。

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

约束条件

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

输入

从标准输入读入输入数据。输入格式如下：

$T$ $\text{case}_1$ $\vdots$ $\text{case}_T$

其中，$\text{case}_i$表示第$i$个测试用例。
每个测试用例的格式如下：

$D$ $K$ $X$

输出

输出结果到标准输出。输出格式如下：

输出$T$行。

第$i$行应包含第$i$个测试用例的答案（一个整数）。

示例输入1

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

1
2
1
1
2
1
0
1
999999999999999998
1
0