#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
int q;
int n, k;
int find_g(int s);
int find_sum(int s, int d) {
  int l = s * (k * k + 1) + d * k + 1;
  int r = l + k - 1;
  int res = (r - l + 1) * (l + r) / 2;
  int g = find_g(s);
  if (g <= l)
    res += k;
  else if (g <= r)
    res += r - g + 1;
  return res;
}
int find_g(int s) {
  if (s == 0) return k * (k + 1) / 2;
  return find_sum(s / k, s % k);
}
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> q;
  while (q--) {
    cin >> n >> k;
    int b = (n - 1) / (k * k + 1);
    int g = find_g(b);
    if (g == n)
      cout << (b + 1) * (k + 1) << '\n';
    else {
      int x = n - b - (g < n);
      cout << x + (x - 1) / k << '\n';
    }
  }
}
