First, we describe an algorithm that finds the optimal answer, and then we prove that it is indeed optimal.

The algorithm is as follows: suppose the current state is described by a pair of numbers $(p, q)$. Without loss of generality, assume $p \leq q$, and let $cnt$ be the number of divisions already performed. We try to update the answer with the value $q - p + cnt$. If the numbers are equal, we stop. Otherwise, we repeat the process with the pair $(p, q / x)$.

Now let us prove its correctness. The key idea of the algorithm is that it is optimal to perform all integer divisions first, and only then make the numbers equal using operations of adding $+1$. Suppose this is not true. Then at some point we applied $+1$ to a number $p$, and then applied $/= x$. Consider two cases:

$\lfloor \frac{p}{x} \rfloor = \lfloor \frac{p + 1}{x} \rfloor$ .

In this case, the $+1$ operation had no effect at all, so it could have been skipped, reducing the total number of operations.

$\lfloor \frac{p}{x} \rfloor + 1 = \lfloor \frac{p + 1}{x} \rfloor$ .

In this case, we can swap the order of operations: first apply $/= x$, and then apply $+1$. The result and the number of operations remain the same, while the desired property holds.

Thus, the lemma is proven, which establishes the correctness of the algorithm.

The time complexity of the solution is $O(\log_x(a) + \log_x(b))$ per test case.

首先，我们描述一个能得出最优解的算法，然后证明它确实是最优的。

算法如下：假设当前状态由一对数字 $(p, q)$ 描述。不失一般性，假设 $p \leq q$，并令 $cnt$ 为已执行的除法次数。我们尝试用值 $q - p + cnt$ 来更新答案。如果两个数字相等，则停止。否则，我们重复该过程，使用对 $(p, q / x)$。

现在我们来证明其正确性。该算法的关键思想是，最优策略是先执行所有整数除法，然后才使用加 $+1$ 的操作使数字相等。假设事实并非如此。那么在某一步，我们对数字 $p$ 应用了 $+1$，然后又应用了 $/= x$。考虑两种情况：

$\lfloor \frac{p}{x} \rfloor = \lfloor \frac{p + 1}{x} \rfloor$ .

在这种情况下，$+1$ 操作完全没有效果，因此可以跳过，从而减少总操作次数。

$\lfloor \frac{p}{x} \rfloor + 1 = \lfloor \frac{p + 1}{x} \rfloor$。

在这种情况下，我们可以交换操作顺序：先执行 $/= x$，再执行 $+1$。结果和操作次数保持不变，同时所需性质成立。

因此，引理得证，这确立了算法的正确性。

每个测试用例的时间复杂度为 $O(\log_x(a) + \log_x(b))$。

solution

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int INF = (int) 1e18;
 
int32_t main() {
    int _;
    cin >> _;
 
    while (_--) {
        int a, b, x;
        cin >> a >> b >> x;
 
        int ans = INF;
        int i = 0;
        while (a != b) {
            if (b > a) {
                swap(a, b);
            }
 
            ans = min(ans, abs(a - b) + i);
            a /= x;
            i++;
        }
 
        ans = min(ans, i);
 
        cout << ans << "\n";
    }
 
    return 0;
}