#include<bits/stdc++.h>

#define int long long

void solve(){

    int n,k;
    std::cin >> n >> k;

    if(n<=k+2){
        std::cout << n <<'\n';
        return ;
    }

    if(k==2){
        int e = 1;
        while(e*2<n+1){
            e *= 2;
        }
        std::cout<<e<<"\n";
        return ;   
    }
    
    // k+2 < n
    int f1 = k; 
    while((f1*k+k-2)/(k-1)<=n+1){
        f1 = (f1*k+k-2)/(k-1);
    }
    std::cout<<f1<<'\n';

}

signed main(){

    
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);
    int t = 1;
    std::cin >> t;
    while(t--)solve();

    return 0;
}