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