#include <bits/stdc++.h>
using namespace std;
int a[101], T, i, j, k, l, tot;
long long s, n, K, x, I, ans;
void turn(long long t) {
  x = I * K * (K * K + 1) + K * K * t + (1 + K) * K / 2 +
      (I * (K * K + 1) + K * t + K -
                   (x > I * (K * K + 1) + K * t + 1
                        ? x
                        : I * (K * K + 1) + K * t + 1) +
                   1 >
               0
           ? I * (K * K + 1) + K * t + K -
                 (x > I * (K * K + 1) + K * t + 1
                      ? x
                      : I * (K * K + 1) + K * t + 1) +
                 1
           : 0);
}
int main() {
  scanf("%d", &T);
  for (; T; --T) {
    scanf("%lld%lld", &n, &K), s = (n - 1) / (K * K + 1);
    x = s, tot = 0;
    while (x) a[++tot] = x % K, x /= K;
    I = 0, x = K * (K + 1) / 2;
    for (i = tot; i >= 1; i--) turn(a[i]), I = I * K + a[i];
    if (n == x)
      ans = (s + 1) * (K + 1);
    else
      ans = n - s - (n >= x) + (n - s - (n >= x) - 1) / K;
    printf("%lld\n", ans);
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}
