#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll sum(ll x, ll y) { return (x + x + y - 1) * y / 2; }
ll find(ll x, ll y) {
  if (!x) return y * (y + 1) / 2;
  ll p = find(x / y, y), rst = x % y;
  ll st = (x / y) * (y * y + 1) + rst * y + 1;
  if (st + y <= p)
    return sum(st, y);
  else
    return sum(st, y) + min(y, st + y - p);
}
int main() {
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    ll n, kk;
    cin >> n >> kk;
    ll tt = (n - 1) / (kk * kk + 1), p = find(tt, kk);
    if (p == n)
      cout << (tt + 1) * (kk + 1) << endl;
    else {
      ll pos = n - tt - 1 + (n < p), t = (n - 1) % (kk * kk + 1) + 1;
      ll cnt = tt * kk + (t - 1 - (n >= p)) / kk;
      cout << pos + cnt << endl;
    }
  }
  return 0;
}
