AT_abc465_d.X to Y

You are given integers $X,Y$, and an integer $K$ that is at least $2$.

There is a variable $x$, which is initially $x=X$. You can perform the following operation on $x$ zero or more times:

• Choose an integer $y$ satisfying $\displaystyle \left\lfloor \frac xK \right\rfloor=y$ or $\displaystyle \left\lfloor \frac yK \right\rfloor=x$, and replace the value of $x$ with $y$.

Here, $\displaystyle \left\lfloor z \right\rfloor$ is defined as the greatest integer not exceeding $z$, for a real number $z$.

Find the minimum number of operations required to make $x=Y$. Under the given constraints, it can be proved that there always exists a way to make $x=Y$ in a finite number of operations.

You are given $T$ test cases; solve each of them.

给你整数 $X$、$Y$ 和一个不小于 $2$ 的整数 $K$。

有一个变量 $x$，其初始值为 $x = X$。你可以对 $x$ 执行以下操作零次或多次：

• 选择一个整数 $y$，满足 $\displaystyle \left\lfloor \frac{x}{K} \right\rfloor = y$ 或 $\displaystyle \left\lfloor \frac{y}{K} \right\rfloor = x$，然后将 $x$ 的值替换为 $y$。

其中，对任意实数 $z$，$\displaystyle \left\lfloor z \right\rfloor$ 表示不超过 $z$ 的最大整数。

求使 $x = Y$ 所需的最少操作次数。在给定约束条件下，可以证明总存在一种方式，在有限步操作内使 $x = Y$。

你将得到 $T$ 组测试用例，请分别求解每组。

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

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

The $i$-th $(1\le i\le T)$ test case $\text{case}_i$ is given in the following format:

$X$ $Y$ $K$

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

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

第 $i$ 个（$1\le i\le T$）测试用例 $\text{case}_i$ 以如下格式给出：

$X$ $Y$ $K$

Output the answers for the test cases in order, separated by newlines.

按顺序输出测试用例的答案，每个答案占一行。

Sample 1 Explanation:
Consider the first test case.

By performing the following operations, $x=Y$ can be achieved in two operations:

• Choose $y=3$. Since $\displaystyle\left\lfloor\frac{x}K \right\rfloor=\left\lfloor\frac{11}3 \right\rfloor=3$, this choice is valid. Then, replace the value of $x$ with $3$.
• Choose $y=9$. Since $\displaystyle\left\lfloor\frac{y}K \right\rfloor=\left\lfloor\frac{9}3 \right\rfloor=3$, this choice is valid. Then, replace the value of $x$ with $9$.

$x=Y$ cannot be achieved in fewer than two operations, so output $2$ on the first line.

Constraints

• $1\le T\le 2\times 10^5$
• $0\le X,Y\le 10^{18}$
• $2\le K\le 10^{18}$
• All input values are integers.

样例 1 解释：
考虑第一个测试用例。

通过执行以下操作，可以在两次操作内使 $x=Y$ 成立：

• 选择 $y=3$。由于 $\displaystyle\left\lfloor\frac{x}K \right\rfloor=\left\lfloor\frac{11}3 \right\rfloor=3$，该选择合法。然后将 $x$ 的值替换为 $3$。
• 选择 $y=9$。由于 $\displaystyle\left\lfloor\frac{y}K \right\rfloor=\left\lfloor\frac{9}3 \right\rfloor=3$，该选择合法。然后将 $x$ 的值替换为 $9$。

无法在少于两次操作内使 $x=Y$ 成立，因此第一行输出 $2$。

约束条件

• $1\le T\le 2\times 10^5$
• $0\le X,Y\le 10^{18}$
• $2\le K\le 10^{18}$
• 所有输入值均为整数。