AT_abc465_d [ABC465D] X to Y

给定整数 $X, Y$ 以及一个大于等于 $2$ 的整数 $K$。 有一个变量 $x$，初始时 $x = X$。你可以对 $x$ 进行以下操作任意次（包括 $0$ 次）： - 选择一个整数 $y$，满足 $ \left\lfloor \frac{x}{K} \right\rfloor = y $ 或 $ \left\lfloor \frac{y}{K} \right\rfloor = x, $，然后将 $x$ 的值替换为 $y$。 这里，对于实数 $z$，$\lfloor z \rfloor$ 表示不超过 $z$ 的最大整数。 请你求出将 $x$ 变为 $Y$ 所需的最少操作次数。题目保证在给定限制下，一定可以在有限次操作内将 $x$ 变为 $Y$。 共有 $T$ 个测试用例，需要对每个用例分别输出答案。

输入从标准输入按以下格式给出： > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 第 $i$ 个测试用例 $\text{case}_i$ 的格式为： > $X \quad Y \quad K$

对于每个测试用例，输出一行答案。

#### 样例解释 1 对于第一个测试用例： 可以通过以下两步将 $x$ 变为 $Y$： 1. 选择 $y = 3$，因为 $\left\lfloor \frac{11}{3} \right\rfloor = 3$，合法。将 $x$ 变为 $3$。 2. 选择 $y = 9$，因为 $\left\lfloor \frac{9}{3} \right\rfloor = 3$，而当前 $x = 3$，所以合法。将 $x$ 变为 $9$。 少于 $2$ 次操作无法做到，因此输出 $2$。 --- ### 数据范围 - $1 \le T \le 2 \times 10^5$ - $0 \le X, Y \le 10^{18}$ - $2 \le K \le 10^{18}$ - 输入的所有值均为整数 --- 由 Deepseek 翻译。