#include <bits/stdc++.h>

using namespace std;


int main() {

    ios_base::sync_with_stdio(0);
    cout.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t--){
        long long n , a;
        cin >> n >> a;
        long long b = n;
        while(__gcd(a , b) > 1 && b > a)
            b--;
        cout << b << endl;
    }

    return 0;
}