题目描述

给定整数 $X$、$Y$ 和一个 $2$ 以上的整数 $K$。

有一个变量 $x$，初始时 $x = X$。你可以对 $x$ 执行任意多次（也可以 $0$ 次）下面的操作：

• 选择一个整数 $y$，使其满足 $\left\lfloor \dfrac{x}{K} \right\rfloor = y$ 或 $\left\lfloor \dfrac{y}{K} \right\rfloor = x$，然后把 $x$ 的值替换成 $y$。

其中对实数 $z$，$\lfloor z \rfloor$ 表示不超过 $z$ 的最大整数（即向下取整）。

请求出把 $x$ 变成 $Y$ 所需的最少操作次数。可以证明在本题约束下一定存在有限次操作的方案。

本题有 $T$ 组测试数据，请对每组分别求解。

输入格式

T
case_1
case_2
...
case_T

其中第 $i$ 组测试数据 $\text{case}_i$ 的格式为：

X Y K

输出格式

依次输出每组测试数据的答案，每个答案占一行。

输入示例 1

4
11 9 3
0 0 2
842 180 7
1948706013487601 48019760148910476 89014537

输出示例 1

2
0
7
5

示例 1 说明

以第 $1$ 组为例（$X = 11$，$Y = 9$，$K = 3$），可以用 $2$ 步完成：

• 取 $y = 3$。因为 $\left\lfloor \dfrac{x}{K} \right\rfloor = \left\lfloor \dfrac{11}{3} \right\rfloor = 3$，这一步合法，于是 $x$ 变成 $3$。
• 取 $y = 9$。因为 $\left\lfloor \dfrac{y}{K} \right\rfloor = \left\lfloor \dfrac{9}{3} \right\rfloor = 3 = x$，这一步合法，于是 $x$ 变成 $9$。

可以证明少于 $2$ 步做不到，所以答案是 $2$。

第 $2$ 组中 $X = Y = 0$，一步都不用做，答案是 $0$。

第 $4$ 组中 $X$、$Y$、$K$ 都非常大，答案可能来自很深的层级，注意所有变量都要用 64 位整数。

约束条件

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