#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, mod = 1e9 + 7;
const long long inf = 2e18;
template <typename A, typename B>
ostream& operator<<(ostream& out, pair<A, B> p) {
  out << "{ " << p.first << ", " << p.second << " }";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> v) {
  out << "[ ";
  for (int i = 0; i < int((v).size()); i++) {
    out << v[i];
    if (i != int((v).size()) - 1) out << " ,";
  }
  out << " ]";
  return out;
}
long long dq[maxn];
long long solve(long long n, long long k) {
  long long ksm = 1ll * k * (k + 1) / 2;
  auto fr = [&](long long x) {
    x -= ksm - k;
    return (x + k - 1) / k;
  };
  auto fl = [&](long long x) {
    x -= ksm - k;
    return x / k;
  };
  vector<pair<long long, long long> > vec;
  vec.push_back({n, n});
  while (vec.back().first >= ksm + k + 1) {
    long long R = fr(vec.back().second + k + 1) - 1,
              L = fl(vec.back().first - k - 1) + k;
    if (L > R) L = R;
    vec.push_back({L, R});
  }
  reverse(vec.begin(), vec.end());
  int L = 0, R = 0;
  long long pt = 0, cnt = 0, ans = 0;
  auto go = [&]() {
    long long sm = 0;
    int chosen = 0;
    while (chosen < k) {
      while (L != R && dq[L] <= pt) ++L;
      long long lim = R != L ? dq[L] : inf;
      long long choose = min(lim - pt - 1, k - chosen);
      if (pt + 1 <= n && n <= pt + choose) {
        ans += n - pt;
        return true;
      }
      sm += 1ll * choose * (pt + 1 + pt + choose) / 2;
      ans += choose;
      chosen += choose;
      pt += choose + (chosen < k);
    }
    ++ans;
    dq[R++] = sm;
    if (sm == n) return true;
    return false;
  };
  while (L == R || dq[R - 1] <= vec[0].second)
    if (go()) return ans;
  int pos = 0;
  while (true) {
    while (pos < int((vec).size()) && vec[pos].second <= pt) pos++;
    if (pos == int((vec).size())) break;
    if (pt < vec[pos].first) {
      while (L != R && dq[L] <= pt) ++L;
      long long bck = -1;
      long long emp = vec[pos].first - pt - 1 - cnt;
      while (L != R && dq[L] < vec[pos].first) bck = dq[L], ++L, --emp;
      cnt = emp / k;
      ans += cnt * (k + 1);
      pt = vec[pos].first - (emp % k) - 1;
      if (pt < bck) --pt, dq[--L] = bck;
    }
    while (pt < vec[pos].second)
      if (go()) return ans;
  }
  assert(0);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  int q;
  cin >> q;
  while (q--) {
    long long n, k;
    cin >> n >> k;
    cout << solve(n, k) << "\n";
  }
  return 0;
}
