#include <bits/stdc++.h>
using namespace std;

void solve() {
    long long n, k;
    cin >> n >> k;

    long long curr = 1;
    long long ans = -1;

    while (curr <= n) {
        long long b = ((curr - 1) / k) * k + k;
        long long step = b / k;
        if (b > n) {
            ans = curr + ((n - curr) / step) * step;
            break;
        }

        curr += ((b - curr) / step) * step;

        long long front = curr + 1;
        long long rear = curr + 2 * step * k + 1;

        while (front < rear) {
            long long mid = (front + rear) / 2;
            long long should = ((mid - 1) / k) + 1;
            long long actual = mid - curr;
            if (actual < should) {
                front = mid + 1;
            } else {
                rear = mid;
            }
        }

        ans = curr;
        curr = front;
    }

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve();
    }

    return 0;
}

  File "answer.code", line 2
    using namespace std;
          ^^^^^^^^^
SyntaxError: invalid syntax