#include <bits/stdc++.h>   using namespace std;   long long t, n, k;   long long f(long long x) {     if (x == 0) return k * (k + 1) / 2;     long long t = x % k, val = f(x / k), ofs = 0;     if (val < k * t + 2) {       ofs = k;     } else if ((t + 1) * k < val) {       ofs = 0;     } else {       ofs = (t + 1) * k - val + 1;     }     return k * (k + 1) / 2 - t + ofs;   }   long long rjesi(long long x) {     long long buk = (x - 1) / (k * k + 1);     long long pos = (k * k + 1) * buk + f(buk);     if (x != pos) {       long long lef = buk + (pos < x);       return (x - 1 - lef) / k - lef + x;     } else {       long long t = buk % k, val = f(buk / k);       if ((t + 1) * k < val) {         return rjesi(buk / k * (k * k + 1) + (t + 1) * k) + 1;       } else {         return rjesi(buk / k * (k * k + 1) + (t + 1) * k + 1) + 1;       }     }   }   int main() {     cin >> t;     while (t--) {       cin >> n >> k;       cout << rjesi(n) <<   n ;     }     return 0;   }   