#include <bits/stdc++.h>
using namespace std;
long long t, n, k;
long long f(long long x) {
  if (x == 0) return k * (k + 1) / 2;
  long long t = x % k, val = f(x / k), ofs = 0;
  if (val < k * t + 2) {
    ofs = k;
  } else if ((t + 1) * k < val) {
    ofs = 0;
  } else {
    ofs = (t + 1) * k - val + 1;
  }
  return k * (k + 1) / 2 - t + ofs;
}
long long rjesi(long long x) {
  long long buk = (x - 1) / (k * k + 1);
  long long pos = (k * k + 1) * buk + f(buk);
  if (x != pos) {
    long long lef = buk + (pos < x);
    return (x - 1 - lef) / k - lef + x;
  } else {
    long long t = buk % k, val = f(buk / k);
    if ((t + 1) * k < val) {
      return rjesi(buk / k * (k * k + 1) + (t + 1) * k) + 1;
    } else {
      return rjesi(buk / k * (k * k + 1) + (t + 1) * k + 1) + 1;
    }
  }
}
int main() {
  cin >> t;
  while (t--) {
    cin >> n >> k;
    cout << rjesi(n) << '\n';
  }
  return 0;
}
