#include <bits/stdc++.h>
using namespace std;
int T, m, p, k, q;
long long n;
long long calc(long long x, long long k) { return (2 * x + k - 1) * k / 2; }
long long find(long long x, long long k) {
  if (!x) return k * (k + 1) / 2;
  long long tmp = find(x / k, k);
  long long tmp2 = (x / k) * (k * k + 1) + (x % k) * k + 1;
  if (tmp2 + k <= tmp)
    return calc(tmp2, k);
  else
    return calc(tmp2, k) + min(k, tmp2 + k - tmp);
}
void solve() {
  scanf("%lld%d", &n, &k);
  long long cnt = (n - 1) / (1ll * k * k + 1), tmp = find(cnt, k);
  if (tmp == n)
    printf("%lld\n", (cnt + 1) * (k + 1)), void();
  else
    printf("%lld\n", n - cnt - 1 + (n < tmp) + cnt * k +
                         ((n - 1) % (1ll * k * k + 1) - (n >= tmp)) / k);
}
int main() {
  scanf("%d", &T);
  while (T--) solve();
}
