Consider the graph with edges between integers that can be replaced from one to another. It turns out that it forms a tree, as follows (the figure illustrates \(K=3\) case). The graph is undirected because the operation is revertible.

Therefore, the answer can be found recursively in the same manner as the algorithm finding the LCA (Lowest Common Ancestor) of a tree:

• If \(X=Y\): the answer is \(0\).
• If \(X<Y\): the answer is \(1\) plus the answer when \((X, Y)\) is \(\displaystyle \left(X,\left\lfloor \frac YK\right\rfloor \right)\).
• If \(X>Y\): the answer is \(1\) plus the answer when \((X, Y)\) is \(\displaystyle \left(\left\lfloor \frac XK\right\rfloor,Y \right)\).

The problem can be solved by directly implementing this algorithm. The complexity is \(\displaystyle O\left(\frac{\log X+\log Y}{\log K}\right)\) per test case.

Sample code (Python3)

input = __import__("sys").stdin.readline

for _ in range(int(input())):
    x, y, k = map(int, input().split())
    ans = 0
    while x != y:
        if x < y:
            x, y = y, x
        x //= k
        ans += 1
    print(ans)