/*** WORK : 省赛\2023gdcpc\G.cpp ***/
/*** TIME : 2024/11/23 18:55 ***/
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define pb push_back
#define se second
#define fi first
#define int long long
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int MOD = (int) 1e9 + 7;
const int INF = INT_MAX;
// L*2 >= r
int gcd(int x,int y){
    return x%y==0 ? y:gcd(y,x%y);
}
void solve() {
    int L,R;
    cin >> L >> R;
    int g = gcd(L,R);
    int mx = 0;
    for(int i=1;i*i<=R;i++){
        if(L%i==0 && R%i==0){
            int a1 = i;
            L/=a1;R/=a1;
            int l=2,r=R,ans=0;
            while(l<=r){
                int mid = l + r >> 1;
                int t = R/mid;
                if(R/t*t - t >= L){
                  r = mid - 1;
                  ans = mid;
                }else{
                    l = mid + 1;
                }
            }
            mx = max(mx,(R/ans)*a1);
            L*=a1;R*=a1;
            // L/=a2;R/=a2;
            // l=2,r=R,ans=0;
            // while(l<=r){
            //     int mid = l + r >> 1;
            //     int t = R/mid;
            //     if(R/t*t - t >= L){
            //       r = mid - 1;
            //       ans = mid;
            //     }else{
            //         l = mid + 1;
            //     }
            // }
            // mx = max(ans,(R/ans)*a2);
            // L*=a2;R*=a2;
        }
    }
    cout << mx << endl;
    
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(12);
    int T = 1;
    cin>>T;
    while (T--)solve();
}