#include <bits/stdc++.h>
using namespace std;
const int MAXK = 16;
const int MAXN = 5010 * MAXK;
long long int k;
void file_io(char *input, char *output) {
  freopen(input, "r", stdin);
  freopen(output, "w", stdout);
}
void fast_io() {
  ios::sync_with_stdio(false);
  cin.tie(0);
}
pair<long long int, long long int> last_sum(long long int n) {
  if (n < k * (k + 1) / 2) {
    return {0, 0};
  }
  long long int start_cnd = (n - k * (k + 1) / 2) / k + 1;
  auto it = last_sum(start_cnd + (k - 1));
  long long int sum_val = it.first;
  long long int sum_cnt = it.second;
  long long int num_prev = (sum_val - sum_cnt) / k;
  long long int pref_size = (sum_val - sum_cnt) % k;
  long long int suff_size = k - pref_size;
  long long int wrap_sum =
      (sum_val - pref_size) * k + k * (k - 1) / 2 + suff_size;
  if (wrap_sum > n)
    return {(sum_val - pref_size - k) * k + k * (k - 1) / 2, num_prev};
  assert(wrap_sum <= n);
  long long int next_sum = (sum_val + suff_size + 1) * k + k * (k - 1) / 2;
  if (next_sum > n)
    return {wrap_sum, num_prev + 1};
  else {
    long long int incr = (n - next_sum) / (k * k);
    return {next_sum + k * k * incr, num_prev + 1 + 1 + incr};
  }
}
long long int solve(long long int n) {
  auto it = last_sum(n);
  long long int sum_val = it.first;
  long long int sum_cnt = it.second;
  if (sum_val == n) return sum_cnt * (k + 1);
  return n - sum_cnt + (n - sum_cnt - 1) / k;
}
void input() {
  int t;
  long long int n;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    cout << solve(n) << endl;
  }
}
int main() {
  fast_io();
  input();
  return 0;
}
