#include <bits/stdc++.h>   using namespace std;   const int __SIZE = 1 << 18;   char ibuf[__SIZE], *iS, *iT;   template <typename T>   inline void read(T &x) {     char ch, t = 0;     x = 0;     while (!isdigit(ch = (iS == iT                               ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),                                  (iS == iT ? EOF : *iS++))                               : *iS++)))       t |= ch ==  - ;     while (isdigit(ch))       x = x * 10 + (ch ^ 48),       ch = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),                         (iS == iT ? EOF : *iS++))                      : *iS++);     x = t ? -x : x;   }   inline int read_int() {     int x;     return read(x), x;   }   inline long long read_ll() {     long long x;     return read(x), x;   }   template <typename T>   inline void chkmin(T &a, T b) {     a = a < b ? a : b;   }   template <typename T>   inline void chkmax(T &a, T b) {     a = a > b ? a : b;   }   const int MAXN = 150010;   const int mod = 998244353;   inline void Add(int &x, int y) { x += y, x -= x >= mod ? mod : 0; }   inline int Mod(int x) { return x >= mod ? x - mod : x; }   inline int fsp(int x, int k = mod - 2) {     int s = 1;     while (k) {       if (k & 1) s = 1LL * s * x % mod;       x = 1LL * x * x % mod, k >>= 1;     }     return s;   }   inline long long S(long long x, long long k) { return (x + x + k - 1) * k / 2; }   inline long long find(long long x, long long k) {     if (!x) return k * (k + 1) >> 1;     long long p = find(x / k, k), rest = x % k;     long long st = (x / k) * (k * k + 1) + rest * k + 1;     if (st + k <= p)       return S(st, k);     else       return S(st, k) + min(k, st + k - p);   }   inline void Solve() {     long long n = read_ll(), k = read_int(), bel = (n - 1) / (k * k + 1);     long long p = find(bel, k);     if (p == n)       cout << (bel + 1) * (k + 1) << endl;     else {       long long pos = n - bel - 1 + (n < p);       long long t = (n - 1) % (k * k + 1) + 1;       long long cnt = bel * k + (t - 1 - (n >= p)) / k;       cout << pos + cnt << endl;     }   }   int main() {     int Case = read_int();     while (Case--) Solve();     return 0;   }   