#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
using llf = long double;
ul T;
ull n;
ul k;
ull find(ull x, ull k) {
  if (x == 0) {
    return k * (k + 1) >> 1;
  }
  ull q = x / k;
  ull r = x % k;
  ull s = find(q, k);
  ull a = r * k + 1;
  ull b = (r + 1) * k;
  if (b < s) {
    return (k * (k + 1) >> 1) - r;
  } else if (a < s) {
    return (k * (k + 1) >> 1) - r + b - s + 1;
  } else {
    return (k * (k + 1) >> 1) - r + k;
  }
}
ull div(ull a, ull b) { return a / b - (a % b == 0); }
ull mod(ull a, ull b) { return a % b + b * (a % b == 0); }
int main() {
  std::scanf("%u", &T);
  for (ul Case = 1; Case <= T; ++Case) {
    std::scanf("%llu%u", &n, &k);
    ull q = n / (ull(k) * k + 1);
    ull r = n % (ull(k) * k + 1);
    if (r == 0) {
      r += ull(k) * k + 1;
      --q;
    }
    ull tmp = find(q, k);
    if (tmp > r) {
      std::printf("%llu\n", q * k * (k + 1) + div(r, k) * (k + 1) + mod(r, k));
    } else if (tmp < r) {
      std::printf("%llu\n",
                  q * k * (k + 1) + div(r - 1, k) * (k + 1) + mod(r - 1, k));
    } else {
      std::printf("%llu\n", (q + 1) * (k + 1));
    }
  }
  return 0;
}
