#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k,C = 0;
int check(int m){
    int res=0;
    while(m>k){
        C++;
        int sub=(m+k-1ll)/k;
        int next=(sub-1ll)*k;
        int t = (m-next)/sub;
        res+= t ;
        m-=t*sub;
        if(m>next){
            m-=sub;
            res++;
        }
        //cout<<m<<" "<<res<<"\n";
    }
    res+=m-1ll;
    return res;
}
void solve() {
    // int n,k;cin>>n>>k;
    // int m=1;
    // while(true){
    //     int p=(m%(k-1ll)==0)?(m/(k-1ll)):(m/(k-1ll)+1ll);
    //     int add=p;
    //     p=p*k-p;
    //     int m1=(p-m)/add*add+m;
    //     if(m1==m)m1+=add;
    //     if(m1>n){
    //         cout<<(n-m)/add*add+m<<"\n";
    //         return;
    //     }
    //     m=m1;
    // }



    cin>>n>>k;
    if(n<=k)cout<<n<<"\n";
    else{
        int l=n-(n+k-1ll)/k+1ll,r=n,p=check(n)-1ll;
        while(l<r){
            int mid=(l+r+1ll)>>1;
            if(check(mid)<=p)l=mid;
            else r=mid-1;
        }
        cout<<l+1ll<<"\n";
    }
    // n=1919810;k=114514;
    // cout<<check(1)<<" "<<check(n)<<"\n";
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t=1;
    cin>>t;
    while (t--) solve();

    std::cerr<<C/1e8<<"\n";
    return 0;
}