#include<cstdio>
using namespace std;
#define LL long long 

LL n, k;
LL cal(LL sum) {
    return ((sum - 1) / ( k - 1)) + 1;
}
LL time = 0;
bool check(LL sum, LL t, LL cnt) {
    time++;
    sum += t * cnt;
    return (cal(sum) > t);
}

void solve() {
    scanf("%lld%lld", &n, &k);
    LL lastr = 1e12;
    LL sum = k;
    while(1) {
        LL t = ((sum - 1) / (k - 1)) + 1;
        LL l = 0, r = ( n - sum + t - 1) / t + 5;
        if(r > lastr) r = lastr;
        while(r - l > 1) {
            LL mid = (l + r) >> 1;
            if(check(sum, t, mid))
                r = mid;
            else l = mid;
        }
        lastr = r;
        sum += t * r;
        if(sum > n) {
            sum -= ((sum - n + t - 1) / t) * t;
            break;
        }
    }
    printf("%lld\n", sum);
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}