#include<bits/stdc++.h>
#define int long long

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;
        while(x<n){
            ll t=(x+k-2)/(k-1);
            ll y=t*(k-1);
				//cout<<t<<' '<<x<<' '<<y<<'\n';
            if(y==x){
                y+=k-1;
               	if(x+t>=n) break;
				x+=t;
				t++;
            }
            if(y>=n){
                x+=t*((n-x)/t);
                break;
            }
            x+=(y-x+t-1)/t*t;
        }
        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();
    }
}