#include <bits/stdc++.h>
using namespace std;
int T;
long long n, k;
long long get(long long x) {
  if (!x) return (1 + k) * k / 2;
  long long prev = x / k, num = x % k;
  long long pos = get(prev);
  long long L = prev * (k * k + 1) + num * k + 1,
            R = prev * (k * k + 1) + num * k + k;
  if (pos < L) L++, R++;
  long long sum = (L + R) * (R - L + 1) / 2;
  if (pos >= L && pos <= R) sum -= pos, sum += R + 1;
  return sum;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> T;
  while (T--) {
    cin >> n >> k;
    long long len = k * k + 1, t = (n - 1) / len;
    long long pos = get(t), npos = (n - 1) % len;
    if (pos == n)
      cout << t / k * k * (k + 1) + (t % k + 1) * (k + 1) << endl;
    else {
      long long tmp = ((pos < n) ? npos - 1 : npos);
      cout << t * k * (k + 1) + tmp / k * (k + 1) + tmp % k + 1 << endl;
    }
  }
  return 0;
}
