#include <bits/stdc++.h>
using namespace std;
inline char nc() {
  return getchar();
  static char buf[100000], *l = buf, *r = buf;
  return l == r && (r = (l = buf) + fread(buf, 1, 100000, stdin), l == r)
             ? EOF
             : *l++;
}
template <class T>
void read(T &x) {
  x = 0;
  int f = 1, ch = nc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 - '0' + ch;
    ch = nc();
  }
  x *= f;
}
long long n, k;
long long B;
long long I0;
int T;
long long I(long long x) {
  if (x == 0) return I0;
  long long i = x / k, t = x % k;
  long long Ii = I(i);
  long long l = i * B + t * k + 1;
  long long r = l + k - 1;
  long long Ix = (l + r) * (r - l + 1) / 2;
  if (Ii <= l)
    Ix += k;
  else if (Ii <= r)
    Ix += r - Ii + 1;
  return Ix;
}
int main() {
  read(T);
  for (int kase = 1; kase <= T; ++kase) {
    read(n), read(k);
    B = k * k + 1;
    I0 = k * (k + 1) / 2;
    long long i = (n - 1) / B;
    long long Ii = I(i);
    if (n == Ii)
      printf("%I64d\n", (i + 1) * (k + 1));
    else {
      long long p = n - i - (Ii < n);
      printf("%I64d\n", p + (p - 1) / k);
    }
  }
  return 0;
}
