#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {

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

    int tt;
    cin >> tt;
    while(tt--){
        ll n , a;
        cin >> n >> a;
        ll b = n;
        while(__gcd(a , b) > 1 && b > a) b--;
        cout << b << '\n';
    }

    return 0;
}