#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
int t;
long long n, k;
long long mn(long long n, long long k) {
  long long lb = max(0LL, n / k - k - 5), ub = n / k + 5;
  while (ub - lb > 1) {
    long long mid = (lb + ub) / 2;
    if ((mid + mid + k - 1) * k / 2 > n)
      ub = mid;
    else
      lb = mid;
  }
  return ub;
}
pair<long long, long long> calc(long long n, long long k) {
  if (n < k * (k + 1) / 2) return make_pair(0, -1e18);
  if (n == k * (k + 1) / 2) return make_pair(1, n);
  long long beg = mn(n, k);
  pair<long long, long long> res = calc(beg + k - 1, k);
  {
    long long num = beg + k - 1 - res.first;
    long long en = beg + k - 1 - (num % k);
    long long be = en - k + 1;
    if (en + 1 <= res.second && res.second <= beg + k - 1) {
      be--;
      en--;
    }
    long long sum = (be + en) * (en - be + 1) / 2;
    if (be <= res.second && res.second <= en) {
      sum -= res.second - be + 1;
    }
    if (sum <= n) {
      return pair<long long, long long>(num / k, sum);
    } else {
      assert(en == beg + k - 1);
      if (sum == (be + en) * (en - be + 1) / 2) {
        long long en = be - 1;
        long long be = en - k + 1;
        sum = (be + en) * (en - be + 1) / 2;
        if (be <= res.second && res.second <= en) {
          sum -= res.second - be + 1;
        }
      } else {
        long long en = be - 2;
        long long be = en - k + 1;
        sum = (be + en) * (en - be + 1) / 2;
        if (be <= res.second && res.second <= en) {
          sum -= res.second - be + 1;
        }
      }
      return pair<long long, long long>(num / k - 1, sum);
    }
  }
}
int main() {
  cin >> t;
  while (t--) {
    scanf("%lld%lld", &n, &k);
    pair<long long, long long> num = calc(n, k);
    if (num.second == n) {
      printf("%lld\n", (k + 1) * num.first);
    } else {
      long long val = n - num.first;
      if (val % k == 0) {
        long long dv = val / k;
        printf("%lld\n", dv * (k + 1) - 1);
      } else {
        long long dv = val / k;
        printf("%lld\n", dv * (k + 1) + val % k);
      }
    }
  }
}
