問題文に記載された操作は、\(K\) 進数を考えることでそれぞれ次のように言い換えることが可能です。

• \(x\) を \(K\) 進数で表現したときの末尾の桁を取り除く
• \(x\) の \(K\) 進数表現の末尾桁に好きな \(0\) 以上 \(K\) 未満の数を追加する

このように言い換えると、次のように操作を行うことが最適であることが言えます。

• \(x\) の \(K\) 進数表現が \(Y\) の \(K\) 進数表現のprefixとなるまで、末尾桁を取り除く操作を行う。その後、\(x\) と \(Y\) が一致するまで末尾桁に数を追加する操作を行う。

最適性は、\(X\) と \(Y\) のprefixで一致しない数については必ず削除操作で取り除く必要があることからこの回数が下界であることが示せます。

したがって、\(X, Y\) の \(K\) 進数表現をそれぞれ求めた桁数を \(x_s, y_s\)、prefixで一致する桁数を \(p\) として、\((x_s - p) + (y_s - p)\) が答えとなります。

下の実装例では、\(K\) 進数での表現をC++の vector<long long> として管理しています。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()

// x を base 進法で表した桁列を返す
vector<ll> to_digits(ll x, ll base) {
    assert(base > 1);
    vector<ll> result;
    while (x > 0) {
        result.emplace_back(x % base);
        x /= base;
    }
    reverse(all(result));
    return result;
}

void solve() {
    ll x,y,k; cin >> x >> y >> k;
    vector<ll> a = to_digits(x, k);
    vector<ll> b = to_digits(y, k);
    ll pre = 0;
    rep(i, min(a.size(), b.size())) {
        if (a[i] != b[i]) break;
        pre++;
    }
    ll ans = (a.size() - pre) + (b.size() - pre);
    cout << ans << '\n';
}

int main() {
    int t; cin >> t;
    rep(i, t) solve();
}