/**
 *    author:  MaGnsi0
 *    created: 21.04.2022 11:34:21
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int64_t n, a;
        cin >> n >> a;
        int64_t b = max((a - 1) * (n / (a - 1)), (a + 1) * (n / (a + 1)));
        for (int64_t i = n; i >= max(n - 100, (int64_t)1); --i) {
            if (a * i / gcd(a, i) >= a * b / gcd(a, b)) {
                b = i;
            }
        }
        cout << b << "\n";
    }
}