ある整数からある整数に置き換えることが可能な場合に辺を結んだグラフを考えると、以下のように木になることが分かります（以下の画像は \(K=3\) の場合です）。無向グラフなのは操作に可逆性があるためです。

したがって、根付き木の LCA を求めるアルゴリズムと同じ要領で、以下のアルゴリズムで答えを再帰的に求めることができます：

• \(X=Y\) である場合：答えは \(0\) である。
• \(X<Y\) である場合：答えは \((X,Y)\) が \(\displaystyle \left(X,\left\lfloor \frac YK\right\rfloor \right)\) である場合の答えに \(1\) 足した値である。
• \(X>Y\) である場合：答えは \((X,Y)\) が \(\displaystyle \left(\left\lfloor \frac XK\right\rfloor,Y \right)\) である場合の答えに \(1\) 足した値である。

以上をそのまま実装することでこの問題に正答することができます。計算量はテストケース毎に \(\displaystyle O\left(\frac{\log X+\log Y}{\log K}\right)\) です。

実装例(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)