#include<bits/stdc++.h>

#define int long long

void solve(){

    int n,k;
    std::cin >> n >> k;
    
    if(k>n){
        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((__int128)(f1*k+k-2)/(k-1)<=n+1){
        f1 = (__int128)(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;
}