1982B.cpp

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define f(x,n) for(ll i = x ; i<n ; i++) 
#define all(x) x.begin(),x.end()  

void solve() {
    ll x,y,k;
    cin>>x>>y>>k;
    while(k>0 && x>1){
        ll steps = y-x%y;
        if(steps>=k){
            x+=k;
            k = 0;
        }
        else{
            x+=steps;
            k-=steps;
        }
        while(x%y == 0){
            x/=y;
        }
    }
    if(k>0){
        k%=(y-1);
        x+=k;
    }
    while(x%y == 0){
        x/=y;
    }
    cout<<x<<endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int tc;
    cin >> tc;
    while (tc--) {
        solve();
    }

    return 0;
}