#include<bits/stdc++.h>

using namespace std;
#define int long long
#define endl '\n'
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5 + 5, M = 2e5 + 5, LGN = 20, mod = 998244353, B = 131, inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f, P = 1000000711;
int n, k;

int calc(int x, int ct) {
    int res = x / k * ct, p = x % k;
    if (p) {
        int d = x / k + 1;
        res += (p - 1) / d + 1;
    }
    return x - res;
}

int f(int x) {
    if (x == 1)return 1;
    int pt = (x + k - 1) / k, l = 1, r = (x - 1) / pt;
    while (l < r) {
        int mid = l + r >> 1;
        if ((x - pt * mid + k - 1) / k < pt)r = mid;
        else l = mid + 1;
    }
    int p = f(x - pt * l), ct = l;
    l = 1, r = x;
    while (l < r) {
        int mid = l + r >> 1;
        if (calc(mid, ct) >= p)r = mid;
        else l = mid + 1;
    }
    return l;
}

void lxllxs() {
    cin >> n >> k;
    cout << f(n) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)lxllxs();
    return 0;
}