#include<bits/stdc++.h>
#define int long long
using namespace std;

int T,n,k;

int sim(int x){
    return x - (x- 1) / k - 1;
}

int cal1(int num){
    int add = (num - 1) / (k-1) + 1;
    return num + add;
    // int t = (num * k) / (k - 1) + 1;
    // t --;
    // while(sim(t) < num) t ++;
    // return t;
}

int cal2(int num){
    int add = num / (k - 1) + 1;
    return num + add;
    // int t = ((num + 1) * k) / (k-1) + 1;
    // t ++;
    // while(sim(t) > num) t--;
    // return t;
}

signed main(){
    cin >> T;
    while(T--){
        cin >> n >> k;
        int rt = sqrt(n);
        if(k <= rt){
            int pos = 1, L = 1, R = 1;
            while(R < n){
                int add = (pos - 1) / (k-1) + 1;
                L = cal1(L);
                R = cal2(R);
                pos += add;
                // cout << L << " " << R << " " << pos << endl;
            }
            cout << pos << endl;
        }
        else{
            int pos = 1, L = 1, R = 1;
            int a1 = 1, a2 = 1, a3 = 1;
            int nxt_L = k, nxt_R = k-1, nxt_p = k;

            while(R < n){
                int rnd1 = (nxt_L - L + a1 - 1) / a1, rnd2 = (nxt_R - R + a2 - 1) / a2, rnd3 = (nxt_p - pos + a3 - 1) / a3;
                int rnd = min(rnd1, min(rnd2, rnd3));

                L += a1 * rnd;
                R += a2 * rnd;
                pos += a3 * rnd;

                if(L >= nxt_L) a1 ++, nxt_L += k-1;
                if(R >= nxt_R) a2 ++, nxt_R = min(n, nxt_R + k-1);
                if(pos >= nxt_p) a3 ++, nxt_p += k-1;
            }
            cout << pos << endl;
        }
    }
}