Problem Statement

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 component with exactly $X$ vertices. At least how many edges must be cut to achieve the objective?

Constraints

• All values in the input are integers.
• $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}$

Input

The input is given from Standard Input in the following format:

T
case_1
\vdots
case_T

Here, $case_i$ denotes the $i$-th test case. Each test case is given in the following format:

D K X

Output

Print $T$ lines. The $i$-th line should contain the answer to the $i$-th test case as an integer.