// Problem: C. Modified GCD
// Contest: Codeforces - Codeforces Beta Round 67 (Div. 2)
// URL: https://codeforces.com/problemset/problem/75/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: jiangXxin
// Create Time:2024-11-06 22:35:35
// 
// Powered by CP Editor (https://cpeditor.org)

/*
   /\__/\
  (o    o)
  /      \
 // ^  ^ \\
///      \\\
  \      /
   \____/
  /\_  _/\
 */
#include<bits/stdc++.h>

#define fir first
#define sec second
#define pb push_back
#define lowbit(X) X&(-X)
#define sz(X) (int)(X).size()
#define all(X) (X).begin(),(X).end()

#define YES cout<<"YES"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define NO cout<<"NO"<<'\n'
#define No cout<<"No"<<'\n'
#define error cout<<"-1"<<'\n'
#define int long long 

using namespace std;
typedef long long unt;
typedef long double ld;
typedef vector<int> vt_int;
typedef vector<char> vt_char;
typedef vector<bool> vt_bool;
typedef vector<long long> vt_unt;
typedef vector<long double> vt_ld;
typedef vector<vector<int> > vvt_int;
typedef vector<vector<char> > vvt_char;
typedef vector<vector<bool> > vvt_bool;
typedef vector<vector<long long> > vvt_unt;
typedef vector<vector<long double> > vvt_ld;

const long long mod=1e9+7;
const long long INF=1152921504606846976;//(2^60)
const long long N=110000;

unt gcd(unt a,unt b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int L,R,pp;

bool check(int x){
	int p1=(L+x-1)/x;
	int l1=p1*x;
	int p2=R/x;
	int r1=p2*x;
	if(l1>R) return false;
	if(r1<L) return false;
	if(l1!=r1) return true;
	return false;
}

void solve(){
	cin>>L>>R;
	int d=R-L;
	pp=R-L;
	// cout<<check(1757472)<<endl;
	if((check(d))){
		cout<<d<<endl;
		return ;
	}
	if(d<=1e6){
		while(d>0){
			if(check(d)){
				cout<<d<<endl;
				return ;
			}
			d--;
		}
	}
	int p1=L/d;
	int ans=0;
	int d1=d;
	while(true){
		d1=L/p1;
		if(check(d1)){
			ans=max(ans,d1);
			break;
		}
		p1++;//p1=21,20,19,18
	}
	int p2=R/d;
	int d2=d;
	while(true){
		d2=R/p2;
		if(check(d2)){
			ans=max(ans,d2);
			break;
		}
		p2++;
	}
	cout<<ans<<endl;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int T=1;cin>>T;
	while(T--) solve();
    return 0;
}