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

typedef long long ll;

int T;

ll n, k;

inline ll _ceil(ll x, ll y) {
	return x / y + !!(x % y);
}

inline ll solve1(ll n, ll k) {
	if (n <= k) {
		return n;
	}
	ll t = solve1(n - _ceil(n, k), k);
	return _ceil(t * k, k - 1);
}

inline ll solve2(ll n, ll k) {
	if (n <= k) {
		return n;
	}
	if (k * k < n) {
		return solve1(n, k);
	}
	ll p = _ceil(n, k), q = _ceil(k, p);
	ll m = n - (p - 1) * q - min((n - 1) % k / p + 1, q);
	ll t = solve2(m, k);
	ll s = (t - 1) / (k - q) + 1, s0 = (t - 1) % (k - q) + 1;
	ll l = 1, r = k;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (mid - min(q, _ceil(mid, s)) >= s0) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return (s - 1) * k + l;
}

inline void solve() {
	cin >> n >> k;
	cout << solve2(n, k) << "\n";
}

int main() {
	#ifdef LOCAL
		assert(freopen("test.in", "r", stdin));
		assert(freopen("test.out", "w", stdout));
	#endif
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}