#include <bits/stdc++.h>
using namespace std;
long long t;
long long fd(long long n, long long k) {
  if (!n) return k * (k + 1) / 2;
  long long v = fd(n / k, k), o = n % k;
  return k * (k + 1) / 2 - o + max(0ll, min(k, (o + 1) * k - v + 1));
}
signed main() {
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    long long x = (n - 1) / (k * k + 1), y = fd(x, k) + (k * k + 1) * x;
    if (y == n)
      cout << (x + 1) * (k + 1) << '\n';
    else {
      n = (n - (n > y) - 1) % (k * k + 1);
      cout << x * k * (k + 1) + n / k * (k + 1) + n % k + 1 << '\n';
    }
  }
}
