#include<bits/stdc++.h>

using namespace std;
using ll=long long ;

void solve(){
    ll n,k;
    cin>>n>>k;
    if(sqrt(n)>=k){
        ll x=1;
        ll pre=1;
        while(x<=n){
            pre=x;
            x=x+(x+k-2)/(k-1);
        }
        cout<<pre<<'\n';
    }
    else{
        ll x=1;
        ll pre;
        while(x<n){
            pre=x;
            ll t=k-1-x%(k-1);
            ll y=(x+k-2)/(k-1);
            x+=(t/y+1)*y;
            //cout<<t<<' '<<y<<' '<<x<<'\n';
            if(x>n){
                x=pre;
                t=(n-x)/y;
                x+=y*t;
                break;
            }
        }
        cout<<x<<'\n';
    }
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cout.tie(nullptr)->sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}