#include using namespace std; typedef long long ll; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b,ll> MA; ll A; ll solve(vector SS,vector T){ priority_queue>,vector>>,greater>>> PQ; PQ.push(mp(0LL,SS)); MA[SS]=0LL; ll res=INF; while(!PQ.empty()){ auto [d,S]=PQ.top();PQ.pop(); if(d>=res) break; if(MA[S] nx; while(now){ nx.push_back(now%A); now/=A; } reverse(all(nx)); if(1){ if(!MA.count(nx)||chmin(MA[nx],d+A+T[au]-x)){ MA[nx]=d+A+T[au]-x; PQ.push(mp(MA[nx],nx)); } } //chmin(res,A+T[au]-x+solve(nx,T)); } if(x>T[au]){ S.back()=T[au]; if(!MA.count(S)||chmin(MA[S],d+x-T[au])){ MA[S]=d+x-T[au]; PQ.push(mp(MA[S],S)); } //chmin(res,x-T[au]+solve(S,T)); S.back()=x; }else if(si(S)>=2){ ll now=0; for(ll a:S){ now*=A; now+=a; } now-=(x+A-T[au]); vector nx; while(now){ nx.push_back(now%A); now/=A; } reverse(all(nx)); if(1){ if(!MA.count(nx)||chmin(MA[nx],d+A+x-T[au])){ MA[nx]=d+A+x-T[au]; PQ.push(mp(MA[nx],nx)); } //chmin(res,(x+A-T[au])+solve(nx,T)); } } } if(x==0){ ll now=0; for(ll a:S){ now*=A; now+=a; } now--; vector nx; while(now){ nx.push_back(now%A); now/=A; } reverse(all(nx)); if(!MA.count(nx)||chmin(MA[nx],d+1)){ MA[nx]=d+1; PQ.push(mp(MA[nx],nx)); } } if(x==A-1){ ll now=0; for(ll a:S){ now*=A; now+=a; } now++; vector nx; while(now){ nx.push_back(now%A); now/=A; } reverse(all(nx)); if(!MA.count(nx)||chmin(MA[nx],d+1)){ MA[nx]=d+1; PQ.push(mp(MA[nx],nx)); } } if(S.back()==0){ S.pop_back(); if(!MA.count(S)||chmin(MA[S],d+1)){ MA[S]=d+1; PQ.push(mp(MA[S],S)); } //chmin(res,1+solve(S,T)); S.push_back(x); }else{ { S.back()=0; if(!MA.count(S)||chmin(MA[S],d+x)){ MA[S]=d+x; PQ.push(mp(MA[S],S)); } //chmin(res,x+solve(S,T)); S.back()=x; } { ll now=0; for(ll a:S){ now*=A; now+=a; } now+=(A-x); vector nx; while(now){ nx.push_back(now%A); now/=A; } reverse(all(nx)); if(!MA.count(nx)||chmin(MA[nx],d+A-x)){ MA[nx]=d+A-x; PQ.push(mp(MA[nx],nx)); } //chmin(res,A-x+solve(nx,T)); } } } return res; } int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); int Q;cin>>Q; while(Q--){ ll s,t;cin>>s>>t>>A; MA.clear(); vector S,T; while(s){ S.push_back(s%A); s/=A; } while(t){ T.push_back(t%A); t/=A; } reverse(all(S)); reverse(all(T)); cout<